单调队列与栈

一.题

1.

思路： 构建小压大的单调递减栈，对于每个栈的元素都进行处理并加到结果上

class Solution {
public:int sumSubarrayMins(vector<int>& arr) {int stk[10000000],top = 0;long long ans = 0;for(int i =0;i<arr.size();i++){while(top&&arr[i]<arr[stk[top-1]]){int cur = stk[--top];int l = top==0?-1:stk[top-1];ans = (ans+(long long)(cur-l)*(i-cur)*arr[cur])%(1000000007);}stk[top++] = i;}while(top){int cur = stk[--top];int l = top==0?-1:stk[top-1];ans = (ans+(long long)(cur-l)*(arr.size()-cur)*arr[cur])%(1000000007);}return ans;}
};

 2.

思路： 以每排都为一次底，然后压缩和第一题类似

#include <vector>
#include <string>
#include <algorithm>
#include <climits>using namespace std;class Solution {
public:int maximalRectangle(vector<string>& matrix) {if (matrix.empty() || matrix[0].empty()) return 0;int rows = matrix.size();int cols = matrix[0].size();vector<int> height(cols, 0); int ans = 0; for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (matrix[i][j] == '1') height[j] += 1;  else height[j] = 0; }int stk[cols + 2], top = 0;stk[top++] = -1; for (int j = 0; j <= cols; j++) {while (top > 1 && (j == cols || height[stk[top - 1]] >= height[j])) {int curHeight = height[stk[--top]]; int width = j - stk[top - 1] - 1; int area = curHeight * width; ans = max(ans, area); }stk[top++] = j; }}return ans;}
};

3.

思路：用单调栈收集每个可能是低点的位置，使得栈严格小压大，单调递增，然后方向遍历全部的元素与栈中元素比较来找距离最远的坡

class Solution {
public:int maxWidthRamp(vector<int>& nums) {int stk[50050],top = 0;int ans = 0;stk[top++] = 0;for(int i =0;i<nums.size();i++){if(nums[i]<nums[stk[top-1]])stk[top++] = i;}for(int i = nums.size()-1;i>=0;i--){while(top&&nums[i]>=nums[stk[top-1]]){int cur = stk[--top];int temp_l = i - cur;ans = max(ans,temp_l);}}return ans;}
};

4.

思路：还是利用单调栈的特性，大压小，开头从栈底部开始，同时用一个数组标记是不是在栈中

#include <string>
#include <vector>using namespace std;class Solution {
public:string removeDuplicateLetters(string s) {int counts[26] = {0}; bool inStack[26] = {false}; char stk[10005];int top = 0; for (char ch : s) counts[ch - 'a']++;for (char ch : s) {if (inStack[ch - 'a']) {counts[ch - 'a']--;continue;}while (top > 0 && stk[top - 1] > ch && counts[stk[top - 1] - 'a'] > 0) {inStack[stk[top - 1] - 'a'] = false; top--; }stk[top++] = ch;inStack[ch - 'a'] = true; counts[ch - 'a']--; }string result;for (int i = 0; i < top; i++) result += stk[i];return result;}
};

 5.

思路：因为，鱼是吃右边的更小的鱼，所以方向遍历后往前，因为小不能吃大，为小压大，在用个cnt数组统计每条鱼进行的场数，用max来求最大值

#include <iostream>
#include <vector>
#include <stack>
using namespace std;int main() {int n,ans = -1;cin>>n;vector<int> fish(n);for(int i = 0; i < n; i++)cin>>fish[i];vector<int> cnt(n,0);stack<int> stk;for(int i = n-1; i >= 0; i--){while(!stk.empty() && fish[i]>fish[stk.top()]){int cur = stk.top();stk.pop();cnt[i] = max(cnt[i]+1,cnt[cur]);  }stk.push(i);ans = max(ans,cnt[i]);}cout<<ans;return 0;
}

 6.算法竞赛进阶指南

思路：模拟过程即可

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include<queue>using namespace std;int main() {int cnt[14];int time[14];vector<vector<char>>tt(14, vector<char>(5, 0));for (int i = 1; i <= 13; i++){cnt[i] = 4; time[i] = 0;for (int j = 1; j <= 4; j++)cin >> tt[i][j];}cnt[13] = 1;while (cnt[13] <= 4) {char temp = tt[13][cnt[13]++];if (temp == 'K') continue;while (temp != 'K') {int num = 0;if (temp == 'A')num = 1;else if (temp == '0')num = 10;else if (temp == 'J')num = 11;else if (temp == 'Q')num = 12;else num = temp - '0';time[num]++;if (cnt[num] == 0)break;temp = tt[num][cnt[num]--];}}int ans = 0;for (int i = 1; i <= 12; i++) {if (time[i] == 4)ans++;}cout << ans;return 0;
}