今天这道每日一题使用单调队列有点绕,特此记录下
题意就是给一个数组,问,有没有3个下标i, j, k, 在满足 i < j < k 的情况下,a_i< a_k < a_j?
单调栈的解题思路就是用单调栈记录当前已经遍历过的最有可能的j的下标,另外记录一个a_k,满足a_k < a_j, 且k > j, 直到找到下标i为止,详情见代码:
-
class Solution {
-
public:
-
bool find132pattern(vector<int>& nums) {
-
int a_k = INT_MIN;
-
int n = nums.size();
-
stack<int> s;
-
for (int i = n-1; i >=0; --i) {
-
if (nums[i] >= a_k) {
-
// 当当前的下标>=a_k的时候,进到这个分支就是要更新j的值
-
while (!s.empty() && nums[s.top()] < nums[i]) {
-
a_k = nums[s.top()];// 弹出a_k
-
s.pop();
-
}
-
s.push(i); // 当前的下标比a_k的下标小,但是值比a_k大
-
} else {
-
return true;
-
}
-
}
-
return false;
-
}
-
};
阅读(1051) | 评论(0) | 转发(0) |