LeetCode 面试题 03.05. 栈排序

Categories:

题目描述
思路分析
1. 解法一：辅助栈（单调栈）（推荐）
相似题目

题目描述

✅ 面试题 03.05. 栈排序

思路分析

解法一：辅助栈（单调栈）（推荐）

核心思路：

维护两个栈：主栈 data 和辅助栈 helper，辅助栈保持从栈底到栈顶单调递减（栈顶最小）

push(val)：将 val 与辅助栈栈顶比较：

若辅助栈为空或 val <= 栈顶，直接压入辅助栈

否则将辅助栈栈顶弹回主栈，重复直到满足条件，再压入辅助栈

pop()：直接弹出辅助栈栈顶（最小值）

peek()：查看辅助栈栈顶

复杂度分析：

时间复杂度：push O(n)，pop/peek O(1)，其中 n 为栈中元素数量

空间复杂度：O(n)，辅助栈最多存储 n 个元素

class SortedStack {

    private Deque<Integer> data;
    private Deque<Integer> helper;

    public SortedStack() {
        data = new ArrayDeque<>();
        helper = new ArrayDeque<>();
    }

    public void push(int val) {
        // 将辅助栈中大于 val 的元素移回主栈
        while (!helper.isEmpty() && helper.peek() < val) {
            data.push(helper.pop());
        }
        helper.push(val);
    }

    public void pop() {
        if (isEmpty()) {
            return;
        }
        // 将主栈元素重新归位到辅助栈
        while (!data.isEmpty()) {
            helper.push(data.pop());
        }
        helper.pop();
    }

    public int peek() {
        if (isEmpty()) {
            return -1;
        }
        // 将主栈元素重新归位到辅助栈
        while (!data.isEmpty()) {
            helper.push(data.pop());
        }
        return helper.peek();
    }

    public boolean isEmpty() {
        return data.isEmpty() && helper.isEmpty();
    }
}

type SortedStack struct {
    data   []int
    helper []int
}

func Constructor() SortedStack {
    return SortedStack{}
}

func (s *SortedStack) Push(val int) {
    // 将辅助栈中大于 val 的元素移回主栈
    for len(s.helper) > 0 && s.helper[len(s.helper)-1] < val {
        s.data = append(s.data, s.helper[len(s.helper)-1])
        s.helper = s.helper[:len(s.helper)-1]
    }
    s.helper = append(s.helper, val)
}

func (s *SortedStack) Pop() {
    if s.IsEmpty() {
        return
    }
    // 将主栈元素重新归位到辅助栈
    for len(s.data) > 0 {
        s.helper = append(s.helper, s.data[len(s.data)-1])
        s.data = s.data[:len(s.data)-1]
    }
    s.helper = s.helper[:len(s.helper)-1]
}

func (s *SortedStack) Peek() int {
    if s.IsEmpty() {
        return -1
    }
    // 将主栈元素重新归位到辅助栈
    for len(s.data) > 0 {
        s.helper = append(s.helper, s.data[len(s.data)-1])
        s.data = s.data[:len(s.data)-1]
    }
    return s.helper[len(s.helper)-1]
}

func (s *SortedStack) IsEmpty() bool {
    return len(s.data) == 0 && len(s.helper) == 0
}

相似题目

题目	难度	考察点
155. 最小栈	中等	栈、辅助栈
316. 去除重复字母	中等	单调栈、贪心
739. 每日温度	中等	单调栈
84. 柱状图中最大的矩形	困难	单调栈
面试题 03.02. 栈的最小值	简单	栈、辅助栈
232. 用栈实现队列	简单	栈、设计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/72157872