栈

栈

栈（Stack） 是一种常见的线性数据结构，具有后进先出（LIFO, Last In First Out）的特点。栈就像生活中的书堆或碟子堆，只能在一端进行操作：新元素从顶端加入，移除时也只能从顶端取出。

用数组模拟栈

#include <iostream>
using namespace std;

const int N = 100010;
int stk[N], tt = -1;

void push(int x)
{
	stk[++tt] = x;
}

void pop()
{
	tt--;
}

void empty()
{
	if (tt == -1) cout << "YES" << endl;
	else cout << "NO" << endl;
}

void query()
{
	cout << stk[tt] << endl;
}

int main()
{	
	int M;
	cin >> M;
	int x;
	while (M--) {
		string op;
		cin >> op;
		if (op == "push") {
			cin >> x;
			push(x);
		} else if (op == "pop") {
			pop();
		} else if (op == "empty") {
			empty();
		} else {
			query();
		}	
	}
 
	return 0;
}

单调栈

暴力

void solve() {
    int n; cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    vector<int> left;
    vector<int> right;
    for (int i = 0; i < n; i++) {
        int pos_l = -1, pos_r = -1;
        for (int j = i; j >= 0; j--) {
            if (arr[j] < arr[i]) {
                pos_l = j;
                break;
            }
        }
        for (int j = i; j < n; j++) {
            if (arr[j] < arr[i]) {
                pos_r = j;
                break;
            }
        }
        if (pos_l != -1) left.push_back(arr[pos_l]);
        else left.push_back(pos_l);
        if (pos_r != -1) right.push_back(arr[pos_r]);
        else right.push_back(pos_r); 
    }
    for (int i = 0; i < n; i++) cout << left[i] << " ";
    cout << endl;
    for (int i = 0; i < n; i++) cout << right[i] << " ";
    cout << endl; 
    // 求每一个位置左边离自己最近且比自己小的数的位置
    // 求每一个位置右边离自己最近且比自己小的数的位置
}

左程云版

void solve() {
    /*
        流程:
        1. 压入数字的时候保证栈底到栈顶的数字由小到大
        2. 栈里存放的是下标
        3. 当有一个不符合条件的数加进来，弹出栈顶
        4. 对于弹出的那个数而言，左边的数是当前栈顶，右边的数是那个不符合条件的数
        5. 如果弹出栈顶之后栈为空，那左边就是 -1。如果最后栈里面还有元素，那么右边的就是 -1
    */
    int n; cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    vector<int> left(n, -1);
    vector<int> right(n, -1);
    stack<int> stk;
    // 求左边最近比自己小的数
	// 如果是求最近且比自己大的数，只需要改成 arr[i] >= arr[stk.top()]
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && arr[i] <= arr[stk.top()]) {
            stk.pop();
        }
        if (!stk.empty()) left[i] = arr[stk.top()];
        stk.push(i);
    }
    // 求右边最近比自己小的数
    while (!stk.empty()) stk.pop();
    for (int i = n - 1; i >= 0; i--) {
        while (!stk.empty() && arr[i] <= arr[stk.top()]) {
            stk.pop();
        }
        if (!stk.empty()) right[i] = arr[stk.top()];
        stk.push(i);
    }
    for (int i = 0; i < n; i++) cout << left[i] << " ";
    cout << endl;
    for (int i = 0; i < n; i++) cout << right[i] << " ";
    cout << endl; 
}

acwing版

https://www.acwing.com/problem/content/832/

#include <iostream>
using namespace std;

const int N = 100010;
int stk[N], tt;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	int N;
	cin >> N;
	while (N--) {
		int x;
		cin >> x;
        //如果栈顶元素大于等于当前待入栈元素，则出栈
		while (tt > 0 && stk[tt] >= x) tt--; 
        //如果栈空，则没有比该元素小的值
		if (tt == 0) cout << -1 << " ";   
        //栈顶元素就是左侧第一个比它小的元素   
		else cout << stk[tt] << " ";	  
        //入栈   
		stk[++tt] = x;					    
	}

	return 0;
}

习题

Colorful Bracket Sequence

https://atcoder.jp/contests/abc394/tasks/abc394_d

#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve() {
    string str; cin >> str;
    stack<char> stk;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '<') {
            stk.push(str[i]);
        } else {
            if (!stk.empty()) {
                if (stk.top() == '(' && str[i] == ')' || stk.top() == '[' && str[i] == ']' || stk.top() == '<' && str[i] == '>') {
                    stk.pop();
                } else {
                    cout << "No" << endl;
                    return;
                }
            } else {
                cout << "No" << endl;
                return;
            }
        }
    }
    if (stk.empty()) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
} 

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

每日温度

https://leetcode.cn/problems/daily-temperatures/description/

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        // 下一次温度升高在第几天，就是寻找比这个数大的第一个数的位置
        // 维护一个单调栈，栈底到栈顶由大到小
        int n = temperatures.size();
        vector<int> ans(n), right(n, -1);
        stack<int> stk;
        for (int i = n - 1; i >= 0; i--) {
            while (!stk.empty() && temperatures[i] >= temperatures[stk.top()]) {
                stk.pop();
            } 
            if (!stk.empty()) right[i] = stk.top();
            stk.push(i);
        }
        for (int i = 0; i < n; i++) {
            if (right[i] != -1) ans[i] = right[i] - i;
        }
        return ans;
    }
};

子数组的最小值之和

https://leetcode.cn/problems/sum-of-subarray-minimums/description/

class Solution {
    const int mod = 1e9 + 7;
public:
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        // 找到每个位置的左边最近且小于这个数的位置
        // 找到每个位置的右边最近且小于这个数的位置
        // 那么中间的所有的区间的最小值就是当前的这个数
        // 每个区间都要过当前的这个数
        // 一个 <= 另一个 < 避免重复贡献
        long long sum = 0;
        vector<int> left(n, -1), right(n, n);
        stack<int> stk;
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && arr[i] <= arr[stk.top()]) {
                stk.pop();
            }
            if (!stk.empty()) left[i] = stk.top();
            stk.push(i);
        }
        while (!stk.empty()) stk.pop();
        for (int i = n - 1; i >= 0; i--) {
            while (!stk.empty() && arr[i] < arr[stk.top()]) {
                stk.pop();
            }
            if (!stk.empty()) right[i] = stk.top();
            stk.push(i);
        }       
        for (int i = 0; i < n; i++) {
            sum = (sum + (long)(i - left[i]) * (right[i] - i) * arr[i] % mod ) % mod;
        }
        return sum;
    }
};

柱状图中的最大矩形

https://leetcode.cn/problems/largest-rectangle-in-histogram/description/

class Solution {
public:
    int largestRectangleArea(vector<int>& arr) {
        // 最大的矩形的高一定是这所有的小矩形的高中的一个
        // 不妨枚举每个数，如果以当前数作为高的最大面积
        // 分别找到左边最近且比当前数小的数，和右边最近且比当前数小的数
        int n = arr.size();
        vector<int> left(n, -1), right(n, n);
        int ans = INT_MIN;
        stack<int> stk;
        // 大压小
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && arr[i] <= arr[stk.top()]) {
                stk.pop();
            }
            if (!stk.empty()) left[i] = stk.top();
            stk.push(i);
        }
        while (!stk.empty()) stk.pop();
        for (int i = n - 1; i >= 0; i--) {
            while (!stk.empty() && arr[i] <= arr[stk.top()]) {
                stk.pop();
            }
            if (!stk.empty()) right[i] = stk.top();
            stk.push(i);
        }
        for (int i = 0; i < n; i++) {
            ans = max(ans, (right[i] - left[i] - 1) * arr[i]);
        }
        return ans;
    }
};

最大矩形

https://leetcode.cn/problems/maximal-rectangle/description/

int largestRectangleArea(vector<int>& arr) {
    // 最大的矩形的高一定是这所有的小矩形的高中的一个
    // 不妨枚举每个数，如果以当前数作为高的最大面积
    // 分别找到左边最近且比当前数小的数，和右边最近且比当前数小的数
    int n = arr.size();
    vector<int> left(n, -1), right(n, n);
    int ans = INT_MIN;
    stack<int> stk;
    // 大压小
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && arr[i] <= arr[stk.top()]) {
            stk.pop();
        }
        if (!stk.empty()) left[i] = stk.top();
        stk.push(i);
    }
    while (!stk.empty()) stk.pop();
    for (int i = n - 1; i >= 0; i--) {
        while (!stk.empty() && arr[i] <= arr[stk.top()]) {
            stk.pop();
        }
        if (!stk.empty()) right[i] = stk.top();
        stk.push(i);
    }
    for (int i = 0; i < n; i++) {
        ans = max(ans, (right[i] - left[i] - 1) * arr[i]);
    }
    return ans;
}

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        // 分别以每一行作为矩形的底
        // 从底开始有多少个连续的 1 就是有多高
        int n = matrix.size();
        int m = matrix[0].size();
        int ans = INT_MIN;
        vector<int> arr(m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0) arr[j] = matrix[i][j] - '0';
                else {
                    // 如果上一行是 1 且当前行也是 1
                    if (matrix[i - 1][j] == '1' && matrix[i][j] == '1') arr[j]++;
                    // 如果上一行是 1 且当前的是0
                    if (matrix[i - 1][j] == '1' && matrix[i][j] == '0') arr[j] = 0;
                    // 如果上一行为 0 且当前行为1
                    if (matrix[i - 1][j] == '0' && matrix[i][j] == '1') arr[j] = 1;
                    // 如果上一行为 0 且当前行也为0
                    if (matrix[i - 1][j] == '0' && matrix[i][j] == '0') arr[j] = 0;
                }
            }
            ans = max(ans, largestRectangleArea(arr));
        }
        return ans;
    }
};