题解 | #单调栈#

单调栈

http://www.nowcoder.com/practice/ae25fb47d34144a08a0f8ff67e8e7fb5

一.题意整合

给定一个长度为n的可能含有重复值的数组arr,找到每一个i位置左边和右边离i位置最近且值比 arri小的位置,若不存在即返回值为-1。

二.思路整理

题目的意思很明了使用单调栈,借助单调性处理问题的思想在于即使排除了不可能的选项,保持策略集合的高度有效性和秩序性。

单调栈:单调栈就是使栈内元素单调递增或者单调递减的栈,单调栈也只能在栈顶操作。

while(栈顶元素比入栈元素小且栈不空){
		栈顶元素弹出
}
元素入栈

首先要知道单调栈入栈的的是下标。对于入栈元素直接入栈会破坏单调性,所以需要栈顶元素出栈,后加入当前元素,使得我们当前的元素再加进去不会破坏它的单调性。

alt

让我们模拟一遍单调栈的运行过程,这里的单调栈是单调递增栈。
我们现在有6个数 4,1,7,9,3,6。
我们当前栈内没有元素,将4加入。现在栈内元素应该是4。
当前元素为1,我们发现加入之后不能单调,于是4出栈,加入1。当前栈内元素为2。
接下来是7,9。我们发现加入不会破坏单调性,于是直接加入,栈内元素1,7,9。
遇到3,只能吐出栈内7,9,加入3。
最后加入6。结束。

对于本题来说需要返回左右的最小值,很显然只需要进行两次遍历,第一次遍历啊超出右边的最小值,然后第二次遍历找出最左边最小值。

三.代码实现

class Solution {
public:
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        vector<vector<int>>ans(nums.size(),vector<int>(2,-1));//记录左右的最小值
        stack<int>st;//栈需要维护单调性
        //找到左边的最小值
        for(int i=0;i<nums.size();i++){
            if(!st.size()){
                st.push(i);
                continue;
            }
            while(st.size()&&nums[st.top()]>nums[i]){
                ans[st.top()][1]=i;//左边最小值的记录
                st.pop();
            }
            st.push(i);
        }
        while(st.size()) st.pop();//栈清空
        //反过来找到右边的最小值
        for(int i=nums.size()-1;i>=0;i--){
            if(!st.size()){
                st.push(i);
                continue;
            }
            while(st.size()&&nums[st.top()]>nums[i]){
                ans[st.top()][0]=i;//右边最小值的记录
                st.pop();
            }
            st.push(i);
        }
        return ans;
    }
};
全部评论

相关推荐

2024-11-15 23:37
门头沟学院 Java
不敢追175女神:和hr偷偷谈对象能不能提高base😋
点赞 评论 收藏
分享
黑皮白袜臭脚体育生:可以看看我的开源仿b站前后端分离微服务项目,技术栈相当先进,符合企业校招需求,具体为springboot security, nacos,openfeign,gateway,redis,elasticsearch,rocketmq,minio,mybatis-plus,mybatis-plus-join,druid,jwt,swagger,gson,hutool,websocket,讯飞星火api,jave,xxl-job,zipkin,slueth,可快速下载所有用到的中间件和远程连接中间件软件而不用麻烦的去官网找包以及只需小改存放路径就可缓存前端静态资源的nginx和前端dist包,无需会任何前端极速实现本机运行前端,所有文档教程只在牛客,有各中间件启动教程,有配套简历写法速成简历,github已经330star
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务