线性结构

单调栈

最大的矩形 CCF201312-3

问题描述

在横轴上放了n个相邻的矩形，每个矩形的宽度是1，而第i（1 ≤ i ≤ n）个矩形的高度是hi。这n个矩形构成了一个直方图。例如，下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3

请找出能放在给定直方图里面积最大的矩形，它的边要与坐标轴平行。对于上面给出的例子，最大矩形如下图所示的阴影部分，面积是10。

输入格式

第一行包含一个整数n，即矩形的数量(1 ≤ n ≤ 1000)。
第二行包含n 个整数h1, h2, … , hn，相邻的数之间由空格分隔。(1 ≤ hi ≤ 10000)。hi是第i个矩形的高度。

输出格式

输出一行，包含一个整数，即给定直方图内的最大矩形的面积。

样例输入

6
3 1 6 5 2 3

样例输出

思路

倘若能够保证元素单调递增，则对于其中任意一个元素来讲，其能画出最大面积的矩形的高度为该元素的大小，宽度为该元素到右边界的长度。

代码

#include<iostream>
#include<stack>
using namespace std;
int a[1005];
int main() {
    stack<int> s;    //单调栈，存放的是数组下标
    int n, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }   //a[0]=0;
    s.push(0);  //首位元素入栈，边界元素
    for (int i = 1; i <= n + 1; i++) {
        //遍历到n+1，也是边界判定
        if (a[i] >= a[s.top()]) {
            s.push(i);    //保证单调递增的特性
        }
        else {  //无法保证单调递增，这个时候开始计算矩形大小
            while (1) {
                int temp = a[s.top()];
                s.pop();
                ans = max(ans, temp * (i - s.top() - 1));    //矩形的高度是当前元素的高度，宽度是当前元素到右边界的长度
                if (s.empty() || a[s.top()] <= a[i]) {    //特判栈空和保证单调性
                    break;
                }
            }
            s.push(i);
        }
    }
    cout << ans << endl;
    return 0;
}

表达式计算

中缀表达式计算

中缀表达式的计算需要我们用两个栈来存储数据：

第一个栈用来存储运算符，第二个栈用来储存操作数。

保证运算符栈从栈顶到栈底运算符的优先级是递减的。如果遇到左括号，直接进栈，如果是右括号，则运算符纷纷出栈和操作数进行运算，直到遇到左括号。其他情况要先判断运算符优先级，如果栈顶运算符优先级较高，则一直弹出栈顶的运算符进行计算直到满足运算符递减要求。

#include<iostream>
#include<stack>
using namespace std;
stack<char> s_oper;    //操作符栈
stack<double> s_num; //操作数栈
int _getlevel(char ch) {
    if (ch == '(') return 0;
    if (ch == '+' || ch == '-') return 1;
    if (ch == '*' || ch == '/') return 2;
    return 3;
}
double cal(char ch, double num1, double num2) {
    if (ch == '+') return num1 + num2;
    if (ch == '-') return num1 - num2;
    if (ch == '*') return num1 * num2;
    if (ch == '/') return num1 / num2;
}
int main() {
    string s;
    cin >> s; //中缀表达式
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] >= '0' && s[i] <= '9') s_num.push(s[i] - '0');  //数字直接进栈，这里只考虑单个数字的情况，如果是多位数的话需要特殊处理
        //是括号的情况下
        else if (s[i] == '(') s_oper.push(s[i]);    //左括号直接进栈
        else if (s[i] == ')') { //右括号就出栈运算符，直到遇到左括号
            while (1) {
                char ch = s_oper.top(); s_oper.pop();
                if (ch == '(') break;  //遇到左括号就停下
                double right = s_num.top(); s_num.pop();
                double left = s_num.top(); s_num.pop();
                s_num.push(cal(ch, left, right));
            }
        }
        //操作符如果需要判断优先级
        else if (s_oper.empty() ||
            _getlevel(s_oper.top()) < _getlevel(s[i])) s_oper.push(s[i]);  //保证操作符栈的优先级从栈顶到栈底递减
        else {
            while (1) {
                if (s_oper.empty() || _getlevel(s_oper.top()) < _getlevel(s[i])) {
                    s_oper.push(s[i]);
                    break;
                }
                char ch = s_oper.top(); s_oper.pop();
                double right = s_num.top(); s_num.pop();
                double left = s_num.top(); s_num.pop();
                s_num.push(cal(ch, left, right));
            }
        }

    }
    //最后处理两个栈当中可能残留的操作符和运算数
    while (!s_oper.empty()) {
        char ch = s_oper.top(); s_oper.pop();
        double right = s_num.top(); s_num.pop();
        double left = s_num.top(); s_num.pop();
        s_num.push(cal(ch, left, right));
    }
    cout << s_num.top();  //最后输出
}

后缀表达式计算

后缀表达式是计算起来最简单的，只需要从左到右遍历过去，遇到数字就入栈，遇到运算符就出两个数字来运算然后重新压回栈中即可。

#include<iostream>
#include<stack>
using namespace std;
stack<double> s_num;    //操作符栈
double cal(char ch, double num1, double num2) {
    if (ch == '+') return num1 + num2;
    if (ch == '-') return num1 - num2;
    if (ch == '*') return num1 * num2;
    if (ch == '/') return num1 / num2;
}
int main() {
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] >= '0' && s[i] <= '9') s_num.push(s[i] - '0');  //数字就直接入栈
        else {
            double right = s_num.top(); s_num.pop();
            double left = s_num.top(); s_num.pop();
            s_num.push(cal(s[i], left, right));
        }
    }
    cout << s_num.top();
    return 0;
}