栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

leetcode:6080. 使数组按非递减顺序排列【单调栈 + 合并】

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

leetcode:6080. 使数组按非递减顺序排列【单调栈 + 合并】

分析

保存一个单调递减的stack,元素是(num, max+t)
遇到大于等于栈顶的,把栈顶的挪出来,然后记录同一次挪出的最大的max_t
如果挪完st还有剩余的话,max_t ++
然后ans就是取所有max_t的最大值
最后把(num, max_t)放到栈顶即可

python code
class Solution:
    def totalSteps(self, nums: List[int]) -> int:
        ans = 0
        st = [] # (num, max_t)

        for num in nums:
            max_t = 0
            # 保持一个单调递减队列
            while st and st[-1][0] <= num:
                max_t = max(max_t, st.pop()[1])
            # 若前面还能保留至少一个
            if st: max_t += 1
            ans = max(ans, max_t)
            # 加入单调栈
            st.append((num, max_t))
        
        return ans
java code
class Solution {
    public int totalSteps(int[] nums) {
        var ans = 0;
        // 用ArrayDeque模拟stack
        var st = new ArrayDeque();

        for(var num: nums) {
            var max_t = 0;
            while(!st.isEmpty() && st.peek()[0] <= num) {
                max_t = Math.max(max_t, st.peek()[1]);
                st.pop();
            }
            if(!st.isEmpty()) max_t++;
            ans = Math.max(ans, max_t);
            st.push(new int[]{num, max_t});
        }

        return ans;

    }
}
总结

ArrayDeque里面放的是int[]
然后有isEmpty(), peek(), pop(), push()等封装好的栈的方法
学到了学到了

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/937400.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号