[数据结构与算法]503. 下一个更大元素 II.Next Greater Element II [单调栈]

By Jalan

知识工具需求

数据结构和算法

单调栈

题干

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/next-greater-element-ii

例子

例1

输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

题解

思路

从第i个位置,循环的往后找size个数,里面有比之大的则填上.没有则-1
方案:

1. 暴力遍历每个数, 从i遍历到(i+size)%size 显然的复杂度是O(n2)
2. 单调栈 O(n)
   说一下单调栈
   看一个很典型的串
   [5,4,3,2,1,4,3]
   其实还是分治.
   假如现在的输入是这个
   这个串可以被分为两个部分,
   从左往后处理
   左侧串a递减,暂时找不到比他大的.
   右侧不定.
   这个时候右侧左边界的数值一定是左侧有边界的一些数值的临近大值,也就是这些数的结果,把这些数字抛去,继续从左往右处理变成下一个子问题.
   我们可以看到,从左往右处理的时候,是后进先出的,所以用栈.
   然后还有个小问题,要循环找右侧第一个比第i个数大的数的时候,
   查找范围(i,n-1]∪[0,i-1]与(i,n-1]∪[0,n-1]的结果是一致的,所以从右往左入栈的处理的时候直接入2n-1次即可.

编写用时

代码

CPP

// @before-stub-for-debug-begin

#include <stack>
#include <string>
#include <vector>
using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=503 lang=cpp
 *
 * [503] 下一个更大元素 II
 */

// @lc code=start
class Solution
{
public:
    vector< int > nextGreaterElements( vector< int >& nums )
    {
        int           size = nums.size();
        vector< int > answer( static_cast< int >( nums.size() ), -1 );
        stack< int >  st;  //栈里是下标喔
        int           i = 0;
        while ( i <= nums.size() * 2 - 1 ) {
            //栈空时直接加入
            if ( st.empty() ) {
                st.push( i % size );
                i++;
                continue;
            }
            //栈顶元素小于当前要加入的元素,将当前要加入的元素作为栈顶元素的答案,出栈,当前要加入的元素不入栈
            if ( nums.at( st.top() ) < nums.at( i % size ) ) {
                answer.at( st.top() ) = nums.at( i % size );
                st.pop();
                continue;
            } else {
                //栈顶元素大于当前要加入的元素,将当前要加入的元素入栈
                st.push( i % size );
                i++;
                continue;
            }
        }
        //栈中剩余元素全找不到,给-1
        return answer;
    }
};
// 5 4 3 2 1 6
// @lc code=end

运行用时

结尾

看在我写了这么多注释的份上可以给我点个赞嘛,求求惹=]砰砰砰,给我加点写下去的油呀
@.@
也欢迎关注我的CSDN账号呀=]

                                        **开心code每一天**