单调栈 & 单调队列



前言

疯狂加了两天数据结构题，可以开始码文了！
单调栈，顾名思义就是具有单调性的栈，其主要用来寻找某个数的左区间向左遍历或右区间向右遍历第一个大于它或小于它的数的位置，具有神奇的复杂度O(n)！
单调队列，与单调栈类似，只不过它是队列，用来求解RMQ问题，和优化DP
优化DP太难了，以后再战 T^T

  1. 单调栈与单调队列
    https://endlesslethe.com/monotone-queue-and-stack-tutorial.html
    https://blog.csdn.net/liujian20150808/article/details/50752861

Largest Rectangle in a Histogram - POJ 2559

题意
给定一个数组，每个元素代表宽为1，高为a[i]的矩形，将他们拼在一起形成一个图形，求此图形中矩形面积最大值
思路
使用单调栈，寻找每个元素左区间向左遍历第一个小于它的数的位置，记为l[i]，右区间同理，记为r[i]，则以该元素为高的矩形面积最大值为a[i]*(r[i]-l[i]-1)，最后选取每个元素为高的矩形面积最大值中的最大值即可

  #include <cstdio>
  #include <iostream>
  #include <algorithm>
  #include <stack>
  using namespace std;
  typedef long long ll;
  const int N = 1e5 + 15;
  const int inf = 0x3f3f3f3f;

  struct Node{
      int val, idx;
      Node(int pval, int pidx): val(pval), idx(pidx) {}
  };

  stack<Node> stk1, stk2;
  int a[N], l[N], r[N];

  inline void init(int n){
      while(!stk1.empty())    stk1.pop();
      while(!stk2.empty())    stk2.pop();
      stk1.push(Node(-inf, -1));
      stk2.push(Node(-inf, n));
  }

  int main(){
      int n;
      while(scanf("%d", &n) && n){
          init(n);
          for(int i = 0; i < n; i++){
              scanf("%d", &a[i]);
          }

          for(int i = 0; i < n; i++){
              while(stk1.top().val >= a[i])    stk1.pop();
              l[i] = stk1.top().idx + 1;
              stk1.push(Node(a[i], i));
          }

          for(int i = n - 1; i >= 0; i--){
              while(stk2.top().val >= a[i])    stk2.pop();
              r[i] = stk2.top().idx - 1;
              stk2.push(Node(a[i], i));
          }

          ll ans = 0;
          for(int i = 0; i < n; i++){
              ans = max(ans, (ll)a[i]*(r[i] - l[i] + 1));
          }
          printf("%lld\n", ans);
      }
  }


Bad Hair Day - POJ 3250

题意
给定一个数组为每头牛的高度h[i]，每头牛可以看见它右边第一头高度比它高的牛的左边所有牛的发型，问所有牛能看见别的牛的发型的数量和
思路
单调栈的运用，比上一题简单

  #include <iostream>
  #include <cstdio>
  #include <algorithm>
  #include <stack>
  using namespace std;
  typedef long long ll;
  const int N = 1e5;
  const int inf = 0x3f3f3f3f;

  struct Node{
      int val, idx;
      Node(int pval, int pidx): val(pval), idx(pidx) {}
  };

  int a[N];
  stack<Node> stk;

  inline void init(int n){
      while(!stk.empty())     stk.pop();
      stk.push(Node(inf, n));
  }

  int main(){
      int n;
      while(~scanf("%d", &n)){
          init(n);
          for(int i = 0; i < n; i++){
              scanf("%d", &a[i]);
          }

          ll sum = 0;
          for(int i = n - 1; i >= 0; i--){
              while(stk.top().val < a[i])     stk.pop();
              sum += (stk.top().idx - i - 1);
              stk.push(Node(a[i], i));
          }
          printf("%lld\n", sum);
      }
  }


Sliding Window - POJ 2823

题意
题意见图中表格即可
思路
使用单调队列，求定长的RMQ

  #include <iostream>
  #include <cstdio>
  #include <algorithm>
  #include <deque>
  using namespace std;
  typedef long long ll;
  const int N = 1e6 + 15;
  const int inf = 0x3f3f3f3f;

  struct Node{
      int val, idx;
      Node(int pval, int pidx): val(pval), idx(pidx) {}
  };

  deque<Node> que;
  int a[N];
  int ansmin[N], ansmax[N];

  int main(){
      int n, k;
      while(~scanf("%d%d", &n, &k)){
          for(int i = 0; i < n; i++){
              scanf("%d", &a[i]);
          }

          while(!que.empty())     que.pop_back();
          for(int i = 0; i < n; i++){
              while(!que.empty() && que.back().val > a[i])   que.pop_back();
              que.push_back(Node(a[i], i));
              if(i + 1 - k >= 0){
                  while(!que.empty() && que.front().idx < i + 1 - k)  que.pop_front();
                  ansmin[i + 1 - k] = que.front().val;
              }
          }

          for(int i = 0; i < n - k + 1; i++){
              printf("%d", ansmin[i]);
              if(i < n - k)   putchar(' ');
          }
          puts("");

          while(!que.empty())     que.pop_back();
          for(int i = 0; i < n; i++){
              while(!que.empty() && que.back().val < a[i])   que.pop_back();
              que.push_back(Node(a[i], i));
              if(i + 1 - k >= 0){
                  while(!que.empty() && que.front().idx < i + 1 - k)  que.pop_front();
                  ansmax[i + 1 - k] = que.front().val;
              }
          }

          for(int i = 0; i < n - k + 1; i++){
              printf("%d", ansmax[i]);
              if(i < n - k)   putchar(' ');
          }
          puts("");
      }
  }