【每日一题】【12.12】2454.下一个更大元素Ⅵ

2023-12-13 05:38:56

🔥博客主页:?A_SHOWY
🎥系列专栏力扣刷题总结录?数据结构??云计算??数字图像处理??力扣每日一题_

2454. 下一个更大元素 IVicon-default.png?t=N7T8https://leetcode.cn/problems/next-greater-element-iv/

?今天的每日一题是一道困难的题目,比较有趣的是,题目要求找“第二大”整数,我们基本可以确定这是一道考察单调栈的题目,因为下一个更大元素这一系列题目都是考察单调栈的使用,但是这个题目略有不同,处理起来也麻烦一些。

总体思路?

这道题目的特殊点其实是要构建一个双单调栈的结构,其中第一个栈stk1用来存储一次比元素大的数也没有的情况(greater,这里我们可以说成见鬼容易理解,一次鬼也没有见过),stk2用来存储见过一次鬼的元素,当见过两次鬼的时候,就会从栈中弹出。

关键一

如上图我们看这两个栈,当输入一个元素的时候,比stk1的第三个和第四个元素大的时候,说明这两个元素见了一次鬼了,只需再见到一次鬼就弹出,所以,移动到stk2中。

关键二

这时,又来了一个紫色元素,比stk2中的第一个小,所以第一个元素留下,比stk2中第二个元素大,第二个元素弹出,那么紫色元素再和stk1中的元素比较,比那两个红色的元素都大,这时候,这两个红色元素要按顺序移动到stk2.

这时候有一个问题就是移动到stk2的栈底还是栈顶,应该是栈顶,因为stk2中的第一个蓝色是因为比紫色大所以才留下,而那两个红色的(stk1)中的因为比紫色小所以弹出到stk2,为了保证这两个单调递减的有序数组所以要放到栈顶。

关键三

那么存放的操作没有什么简单的方法,申请一个数组暂存一下,再reverse后弹出到stk2 中是一个合适的解决方法,注意最后这个紫色的还是要存在stk1中,而不是stk2.

?

那么思路清晰了,整体程序就能写出来:?

class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& nums) {
        stack<int> stk1;
        stack<int> stk2;

    vector<int> res(nums.size(), -1);
    for(int i = 0; i < nums.size(); i++)
    {
        while(!stk2.empty() && nums[stk2.top()] < nums[i]){//栈顶不为空,且比栈顶大
            res[stk2.top()] = nums[i];
            stk2.pop();
        }
        vector<int> temp;//存放,转换位置使用
        while(!stk1.empty() && nums[stk1.top()] < nums[i]){
            //把满足条件的弹出移动到stk1里面,这里要注意顺序,所以要先定义一个数组
          temp.push_back(stk1.top());
          stk1.pop();
        }
        //这时候要翻转一下
        reverse(temp.begin(),temp.end());
        //然后把数组中的放到stk2中
        for(int x: temp) stk2.push(x);
        //最后别忘了新元素还是要放到stk1里面
        stk1.push(i);
    }
    return res;
    }
};

1.定义两个栈,一个结果数组

2.

while(!stk2.empty() && nums[stk2.top()] < nums[i]){//栈顶不为空,且比栈顶大

这里的判定要比较熟悉了,栈顶不为空,同时比栈顶大

3.注意当上文中我们说到的那种紫色的元素出现时,要把要弹出的元素先存放到数组中,反转后再push给stk2.

reverse(temp.begin(),temp.end());
        //然后把数组中的放到stk2中
        for(int x: temp) stk2.push(x);

4.最后不要忘了把新元素放回到stk1中。

整体下来思路还是比较清晰流畅的,虽然是困难难度的题目,但是仍然能够较为简单的解决。

每日一题第三天打卡

文章来源:https://blog.csdn.net/showy0/article/details/134953675
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。