nums라는 숫자 목록이 있다고 가정하고 i

따라서 입력이 nums =[2, 12, 1, 4, 4]와 같으면 2 <4 <12이므로 [2, 12, 4]가 기준과 일치하므로 출력은 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=숫자 크기

• 크기가 n

  인 배열을 정의합니다.

• 왼쪽[0] :=숫자[0]

• initialize i :=1의 경우, i

  • left[i] :=nums[i] 및 left[i - 1]의 최소값

• 하나의 스택 정의

• initialize i :=n - 1의 경우 i>=1일 때 업데이트(i를 1만큼 감소), −

  • x :=왼쪽[i - 1]

  • st가 비어 있지 않고 st <=x의 맨 위에 있는 동안 −

    • 성에서 팝

  • st가 비어 있지 않고 x st의 맨 위이면 -

    • true를 반환

  • 숫자[i]를 st

    로 푸시

• 거짓을 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool solve(vector<int>& nums) {
      int n = nums.size();
      vector<int> left(n);
      left[0] = nums[0];
      for (int i = 1; i < n; i++) {
         left[i] = min(nums[i], left[i - 1]);
      }
      stack<int> st;
      for (int i = n - 1; i >= 1; i--) {
         int x = left[i - 1];
         while (!st.empty() && st.top() <= x)
            st.pop();
         if (!st.empty() && x < nums[i] && nums[i] > st.top())
            return true;
         st.push(nums[i]);
      }
      return false;
   }
};
bool solve(vector<int>& nums) {
   return (new Solution())->solve(nums);
}
int main(){
   vector<int> v = {2, 12, 1, 4, 4};
   cout << solve(v);
}

입력

{2, 12, 1, 4, 4}

출력

1