Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1878279
  • 博文数量: 184
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2388
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(184)

文章存档

2021年(26)

2020年(56)

2019年(54)

2018年(47)

2017年(1)

我的朋友

分类: C/C++

2021-03-24 23:25:47

今天这道每日一题使用单调队列有点绕,特此记录下

题意就是给一个数组,问,有没有3个下标i, j, k, 在满足 i < j < k 的情况下,a_i< a_k < a_j?
单调栈的解题思路就是用单调栈记录当前已经遍历过的最有可能的j的下标,另外记录一个a_k,满足a_k < a_j, 且k > j, 直到找到下标i为止,详情见代码:

点击(此处)折叠或打开

  1. class Solution {
  2. public:
  3. bool find132pattern(vector<int>& nums) {
  4.     int a_k = INT_MIN;
  5.     int n = nums.size();
  6.     stack<int> s;
  7.     for (int i = n-1; i >=0; --i) {
  8.         if (nums[i] >= a_k) {
  9.             // 当当前的下标>=a_k的时候,进到这个分支就是要更新j的值
  10.             while (!s.empty() && nums[s.top()] < nums[i]) {
  11.                 a_k = nums[s.top()];// 弹出a_k
  12.                 s.pop();
  13.             }
  14.             s.push(i); // 当前的下标比a_k的下标小,但是值比a_k大
  15.         } else {
  16.             return true;
  17.         }
  18.     }
  19.     return false;
  20. }
  21. };


阅读(1051) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~