leetcode 面试题 03.05. 栈排序

zhaojun

2022 年 09 月 26 日

3165 次浏览

暂无评论

2501字数

默认分类

# [面试题 03.05. 栈排序](https://leetcode.cn/problems/sort-of-stacks-lcci/)

## 题目

栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：`push`、`pop`、`peek` 和 `isEmpty`。当栈为空时，`peek` 返回 -1。

**示例1:**

```
 输入：
["SortedStack", "push", "push", "peek", "pop", "peek"]
[[], [1], [2], [], [], []]
 输出：
[null,null,null,1,null,2]
```

**示例2:**

```
 输入： 
["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
[[], [], [], [1], [], []]
 输出：
[null,null,null,null,null,true]
```

**说明:**

1. 栈中的元素数目在[0, 5000]范围内。

## 题解

解题思路，将数据栈命名为 dataStack, 辅助栈命名为 helperStack.

1. push: 永远 push 到 dataStack 中.
2. pop: sort() 后, 如果 helperStack 不为空则 pop();
3. peek: sort() 后, 如果 helperStack 不为空则 peek(), 为空返回 -1;
4. isEmpty: 判断 dataStack 和 helperStack 是否都不为空.
5. sort: 排序操作，将 dataStack 排序后压入到 helperStack
   5.1 取 dataStack 中栈顶元素即为 dataTopItem
   5.2 如果 dataTopItem 小于等于 helperStack 栈顶元素，则将 dataTopItem 压入到 helperStack 栈顶.
   5.3 如果 dataTopItem 大于 helperStack 栈顶元素，则依次将 helperStack 栈顶元素压回 dataStack, 然后比较 helperStack 新的栈顶元素和 dataTopItem 的大小，参考 5.2 的逻辑。 直到最后 dataStack 中的元素全部压入到 helperStack 中.

```java
import java.util.Stack;

//leetcode submit region begin(Prohibit modification and deletion)
class SortedStack {
    
    private Stack<Integer> dataStack;
    
    private Stack<Integer> helperStack;
    
    public SortedStack() {
        dataStack = new Stack<>();
        helperStack = new Stack<>();
    }
    
    public void push(int val) {
        dataStack.push(val);
    }
    
    public void pop() {
        sort();
        if (!helperStack.isEmpty()) {
            helperStack.pop();
        }
    }
    
    public int peek() {
        sort();
        if (helperStack.isEmpty()) {
            return -1;
        } else {
            return helperStack.peek();
        }
    }
    
    public boolean isEmpty() {
        return dataStack.isEmpty() && helperStack.isEmpty();
    }
    
    private void sort() {
        if (dataStack.isEmpty()) {
            return;
        }
        
        while (!dataStack.isEmpty()) {
            // 取数据栈栈顶元素
            Integer dataTopItem = dataStack.pop();
    
            // 判断只要辅助栈有元素小于数据栈栈顶元素，则取出并压回数据栈.
            while (!helperStack.isEmpty() && helperStack.peek() < dataTopItem) {
                dataStack.push(helperStack.pop());
            }
            // 确保辅助栈没有比数据栈顶元素小的元素，则压入到辅助栈
            helperStack.push(dataTopItem);
        }
    }
}
```

最后修改：2022 年 09 月 26 日

如果觉得我的文章对你有用，请我喝杯咖啡吧。

leetcode 面试题 03.05. 栈排序

zhaojun • 2022 年 09 月 26 日

leetcode 面试题 03.05. 栈排序

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

谈裸辞和开源的体会

剑指 Offer 04. 二维数组中的查找

Shiro 学习 04 - 加密

通过 Github Actions 自动构建 ZFile 镜像并推送到 Docker Hub

优化 Java 项目 Docker 镜像内存占用从 500 M 到 100M

代码命名之 Spring

Spring 技巧 - @Value 复用

Shiro 学习 04 - 加密

一款基于 Shiro 的权限管理系统，支持 restful 风格 URL.

剑指 Offer 04. 二维数组中的查找

leetcode 面试题 03.05. 栈排序

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

leetcode 面试题 03.05. 栈排序

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款