LeetCode 补充题 24. 双栈排序

Categories:

题目描述
思路分析
1. 解法一：辅助栈插入排序（推荐）
相似题目

题目描述

✅ 补充题 24. 双栈排序

思路分析

解法一：辅助栈插入排序（推荐）

核心思路：

用辅助栈维护有序序列（从栈顶到栈底递增）。

每次从原栈弹出元素 cur，把辅助栈中比 cur 大的元素放回原栈。

最终辅助栈即为排序结果，再转回原栈即可。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示栈元素数量。

空间复杂度：O(n)，需要辅助栈。

class Solution {
    public Stack<Integer> sortStack(Stack<Integer> stack) {
        Stack<Integer> helper = new Stack<>();

        while (!stack.isEmpty()) {
            int cur = stack.pop();

            // 把比 cur 大的元素挪回原栈
            while (!helper.isEmpty() && helper.peek() > cur) {
                stack.push(helper.pop());
            }

            helper.push(cur);
        }

        // 恢复到原栈（栈顶最小）
        while (!helper.isEmpty()) {
            stack.push(helper.pop());
        }

        return stack;
    }
}

func sortStack(stack []int) []int {
    helper := make([]int, 0)

    for len(stack) > 0 {
        cur := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        // 把比 cur 大的元素挪回原栈
        for len(helper) > 0 && helper[len(helper)-1] > cur {
            stack = append(stack, helper[len(helper)-1])
            helper = helper[:len(helper)-1]
        }

        helper = append(helper, cur)
    }

    // 恢复到原栈（栈顶最小）
    for len(helper) > 0 {
        stack = append(stack, helper[len(helper)-1])
        helper = helper[:len(helper)-1]
    }

    return stack
}

相似题目

题目	难度	考察点
155. 最小栈	简单	辅助栈
716. 最大栈	困难	辅助栈
232. 用栈实现队列	简单	双栈模拟
225. 用队列实现栈	简单	队列模拟
496. 下一个更大元素 I	简单	单调栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/15281458