单调栈

https://blog.csdn.net/lucky52529/article/details/89155694

单调栈的伪代码

stack<int> st;
//此处一般需要给数组最后添加结束标志符，具体下面例题会有详细讲解
for (遍历这个数组)
{
    if (栈空 || 栈顶元素大于等于当前比较元素)
    {
        入栈;
    }
    else
    {
        while (栈不为空 && 栈顶元素小于当前元素)
        {
            栈顶元素出栈;
            更新结果;
        }
        当前数据入栈;
    }
}

也可以是这样

单调栈的伪代码
先定义栈中是递增 or 递减。

for（）{

　　while（）{
　　　　pop（）；出栈
　　　　数据处理

　　}
　　push（i）；入栈
}

这个思想来自于

https://www.nowcoder.com/practice/2a2c00e7a88a498693568cef63a4b7bb?tpId=101&&tqId=33256&rp=1&ru=/ta/programmer-code-interview-guide&qru=/ta/programmer-code-interview-guide/question-ranking

题目描述

给定一个可能含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。

输入描述:

第一行输入一个数字 n，表示数组 arr 的长度。
以下一行输入 n 个数字，表示数组的值

输出描述:

输出n行，每行两个数字 L 和 R，如果不存在，则值为 -1，下标从 0 开始。

示例1

输入

复制

7
3 4 1 5 6 2 7

输出

复制

#include <vector>
#include <iostream>
#include <stack>
#include <stdio.h>
using namespace std;
 
int main() {
    int n;
    scanf("%d",&n);
    vector<int>datas(n);
    vector<int>left_idx(n,-1);
    vector<int>right_idx(n,-1);
    
    stack<int>st;
    stack<int>st1;
    
    
 
    for(int i=0;i<n; i++){
        scanf("%d",&datas[i]);
    }
    
    for(int i=0; i<n; i++){

        while(!st.empty()&& datas[st.top()]>= datas[i]){
            st.pop();
        }
        if(!st.empty()){
            left_idx[i] = st.top();
        }
        st.push(i);
    }
    for(int i=n-1;i>=0;i--){
         while(!st1.empty()&& datas[st1.top()]>= datas[i]){
            st1.pop();
        }
        if(!st1.empty()){
            right_idx[i] = st1.top();
        }
        st1.push(i);
    }
    for(int i=0;i<n;i++){
        printf("%d %d
", left_idx[i], right_idx[i]);
        
    }
    return 0;

}

View Code

针对这个问题：

单调栈的应用我们直接拿一些具体的题来对照应用：
1.视野总和

描叙：有n个人站队，所有的人全部向右看，个子高的可以看到个子低的发型，给出每个人的身高，问所有人能看到其他人发现总和是多少。
输入：4 3 7 1
输出：2
解释：个子为4的可以看到个子为3的发型，个子为7可以看到个子为1的身高，所以1+1=2
思路：观察题之后，我们发现实际上题目转化为找当前数字向右查找的第一个大于他的数字之间有多少个数字，然后将每个

结果累计就是答案，但是这里时间复杂度为O(N^2)，所以我们使用单调栈来解决这个问题。

1.设置一个单调递增的栈（栈内0~n为单调递减）
2.当遇到大于栈顶的元素，开始更新之前不高于当前人所能看到的值

#include<stdio.h>
#include <iostream>
#include<fstream>
#include <stack>
#include<vector>
#include<limits.h>
using namespace std;
int fieldSum1(vector<int>&v);
int fieldSum2(vector<int>&v);


int main(){

int a[]={4,3,7,1};
vector<int> test(a,a+4);
cout<<fieldSum1(test)<<endl;
cout<<"-------"<<endl;
cout<<fieldSum2(test)<<endl;
cout<<"end"<<endl;
return 0;

}

int fieldSum1(vector<int>&v){
    
    stack<int>st;
    int sum=0;
    v.push_back(INI_MAX);
    for(int i=0; i<v.size();i++){
    
        while(!st.empty() && v[st.top()] < v[i]){
            int idx = st.top();
            sum += (i-1-idx);
            st.pop();
            
        }
        st.push(i);
    }
    
return sum;    
}


int fieldSum2(vector<int>& v)
{
    
    v.push_back(INI_MAX);
    
    stack<int> st;
    int sum = 0;
    for (int i = 0; i < (int)v.size(); i++)
    {
        if (st.empty() || v[st.top()] > v[i])//小于栈顶元素入栈
        {
            st.push(i);
        }
        else
        {
            while (!st.empty() && v[st.top()] <= v[i])
            {
                int top = st.top();//取出栈顶元素
                st.pop();
                sum += (i - top - 1);//这里需要多减一个1
            }
            st.push(i);
        }
    }
    return sum;
}