栈

一、数组模拟栈

  1. // tt表示栈顶
  2. int stk[N], tt = 0;
  4. // 向栈顶插入一个数
  5. stk[ ++ tt] = x;
  7. // 从栈顶弹出一个数
  8. tt -- ;
  10. // 栈顶的值
  11. stk[tt];
  13. // 判断栈是否为空
  14. if (tt > 0)
  15. {
  17. }

二、单调栈

通过对栈的某些数据进行删除，达到栈中存储的数据呈现单调性

模板

  1. 常见模型：找出每个数左边离它最近的比它大/小的数
  2. int tt = 0;
  3. for (int i = 1; i <= n; i ++ )
  4. {
  5.     while (tt && check(stk[tt], i)) tt -- ;
  6.     stk[ ++ tt] = i;
  7. }

例题

https://www.acwing.com/activity/content/problem/content/865/
image.png

因为找出每个数左边离它最近的比它小的数，所以如果代表着若n[x]>=n[y]，且x<y,那么n[x]不会被输出，所以使用单调栈，在往栈里存数据的时候，如果栈顶元素比当前元素大，则直接删去

  1. import java.util.Scanner;
  2. public class Main{
  3.     public static void main(String[] args) {
  4.         Scanner in = new Scanner(System.in);
  5.         int n = in.nextInt();
  6.         int[] stk = new int[n];
  7.         int tt = 0;
  8.         for(int i = 0;i<n;i++) {
  9.             int x = in.nextInt();
  10.             while(tt != 0 && stk[tt] >= x) tt--;
  11.             if(tt != 0) System.out.print(stk[tt]+" ");
  12.             else System.out.print("-1 ");
  13.             stk[++tt] = x;
  14.         }
  15.     }
  16. }

队列

一、数组模拟队列

1、普通队列

  1. // hh 表示队头，tt表示队尾,q[]存的是下标
  2. int q[N], hh = 0, tt = -1;
  4. // 向队尾插入一个数
  5. q[ ++ tt] = x;
  7. // 从队头弹出一个数
  8. hh ++ ;
  10. // 队头的值
  11. q[hh];
  13. // 判断队列是否为空
  14. if (hh <= tt)
  15. {
  17. }

2、循环队列

  1. // hh 表示队头，tt表示队尾的后一个位置
  2. int q[N], hh = 0, tt = 0;
  4. // 向队尾插入一个数
  5. q[tt ++ ] = x;
  6. if (tt == N) tt = 0;
  8. // 从队头弹出一个数
  9. hh ++ ;
  10. if (hh == N) hh = 0;
  12. // 队头的值
  13. q[hh];
  15. // 判断队列是否为空
  16. if (hh != tt)
  17. {
  19. }

二、单调队列（滑动窗口）O(nk)->O(n)

例题

https://www.acwing.com/problem/content/156/
image.png
image.png

思想

若用普通队列来做的话，每次移入元素进入窗口队列后，还要对窗口中的数进行遍历才能求出最值，遍历的时间复杂度是O(k)，移动次数是n-k+1次，所以如果是普通队列，则时间复杂度为O(nk)

单调队列的思想来做这道题（求最大值的过程），视频讲解 ，优化后时间复杂度为O(n)：
image.png

实现过程

image.png

核心代码（模板）
  1. for (int i = 0;i<n;i++) {
  2.     // q[hh]不在窗口[i-k+1, i]内，队头出队，每次出队只用出一个，所以用if
  3.     if (hh<=tt && q[hh] < i - k + 1) hh++;
  4.     // 当前值<=队尾值，队尾出队 ，直到队空，所以用循环
  5.     while (hh <= tt && a[q[tt]] <= a[i]) tt--;
  6.     q[++ tt] = i;
  7.     // 判断条件保证队列中有三个值。注意i是从0开始
  8.     if (i >= k - 1) System.out.print(a[q[hh]] + " ");
  9. }

用deque实现
  1. class Solution {
  2.     public:
  3.     vector<int> maxInWindows(vector<int>& nums, int k) {
  4.         deque<int> q;
  5.         vector<int> res;
  6.         int n = nums.size();
  8.         for(int i=0;i<n;i++) {
  9.             if(q.size() && q.front() < i-k+1) q.pop_front();
  10.             while(q.size() && nums[i] >= nums[q.back()]) q.pop_back();
  11.             q.push_back(i);
  12.             if(i>=k-1) res.push_back(nums[q.front()]);
  13.         }
  15.         return res;
  16.     }
  17. };