[LeetCode] 716. Max Stack

Design a max stack data structure that supports the stack operations and supports finding the stack's maximum element.

Implement the MaxStack class:

• MaxStack() Initializes the stack object.
• void push(int x) Pushes element x onto the stack.
• int pop() Removes the element on top of the stack and returns it.
• int top() Gets the element on the top of the stack without removing it.
• int peekMax() Retrieves the maximum element in the stack without removing it.
• int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

Example 1:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

Explanation
MaxStack stk = new MaxStack();
stk.push(5);   // [5] the top of the stack and the maximum number is 5.
stk.push(1);   // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5);   // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top();     // return 5, [5, 1, 5] the stack did not change.
stk.popMax();  // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top();     // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop();     // return 1, [5] the top of the stack and the max element is now 5.
stk.top();     // return 5, [5] the stack did not change.

Constraints:

• -107 <= x <= 107
• At most 104 calls will be made to push, pop, top, peekMax, and popMax.
• There will be at least one element in the stack when pop, top, peekMax, or popMax is called.

Follow up: Could you come up with a solution that supports O(1) for each top call and O(logn) for each other call? 

最大栈。

设计一个支持push，pop，top，peekMax和popMax操作的最大栈。

1. push(x) -- 将元素x添加到栈中。
2. pop() -- 删除栈中最顶端的元素并将其返回。
3. top() -- 返回栈中最顶端的元素。
4. peekMax() -- 返回栈中最大的元素。
5. popMax() -- 返回栈中最大的元素，并将其删除。如果有多于一个最大的元素，只删除最靠近顶端的一个元素。

1. -1e7 <= x <= 1e7
2. 操作的个数不会超过10000.
3. 当栈为空时，后面四个操作不会被调用。

这是一道设计题，类似，但是比155题要难得多。 

题意不难理解，思路如下，这里我们需要两个 stack，一个普通的栈 stack 存放所有需要处理的元素，另一个栈 maxStack 只存放当前遍历到的最大的元素，所以在任一时间点，maxStack 的顶端永远都是当前你处理过的元素中最大的那一个。

push() - 因为我们需要满足 maxStack 的栈顶永远是当前遍历到的最大元素，所以我们在做 push 操作的时候，对于每个元素 x，我们需要判断 x 是否大于当前的最大值 curMax，如果是，则更新 curMax 且将 curMax 放到 maxStack 中。这里 push() 操作的复杂度是 O(1)

pop() - 对两个栈都仅做 pop() 操作，复杂度是 O(1)

top() - 查看 stack 的顶端元素，复杂度是 O(1)

peekMax() - 查看 maxStack 的顶端元素，复杂度是 O(1)

popMax() - popMax() 的定义是返回栈中最大的元素，并将其删除。如果有多于一个最大的元素，只删除最靠近顶端的一个元素。因为 maxStack 的顶端一定是栈中最大的元素 max，所以对于 maxStack 而言，我们做一下 pop() 操作即可。但是对于 stack 而言，这个最大的元素不一定在 stack 的顶端，所以这里我们还需要创建一个临时的栈 temp 来存放从 stack 中弹出的所有元素，直到遇到 max 为止。从 stack 和 maxStack 中弹出 max 之后，我们再将 temp 中的元素再 push 回 stack 中，这样我们就做到了仅从 stack 中去除栈中最大的元素 max而不影响到其他元素的效果。这个操作的复杂度是 O(n)

Java实现

 1 class MaxStack {
 2     Stack stack;
 3     Stack maxStack;
 4 
 5     public MaxStack() {
 6         stack = new Stack<>();
 7         maxStack = new Stack<>();
 8     }
 9     
10     public void push(int x) {
11         helper(x);
12     }
13     
14     public void helper(int x) {
15         int curMax = maxStack.isEmpty() ? Integer.MIN_VALUE : maxStack.peek();
16         if (x > curMax) {
17             curMax = x;
18         }
19         stack.push(x);
20         maxStack.push(curMax);
21     }
22 
23     public int pop() {
24         maxStack.pop();
25         return stack.pop();
26     }
27     
28     public int top() {
29         return stack.peek();
30     }
31     
32     public int peekMax() {
33         return maxStack.peek();
34     }
35     
36     public int popMax() {
37         int max = maxStack.peek();
38         Stack temp = new Stack<>();
39         while (stack.peek() != max) {
40             temp.push(stack.pop());
41             maxStack.pop();
42         }
43         stack.pop();
44         maxStack.pop();
45         while (!temp.isEmpty()) {
46             int x = temp.pop();
47             helper(x);
48         }
49         return max;
50     }
51 }
52 
53 /**
54  * Your MaxStack object will be instantiated and called as such:
55  * MaxStack obj = new MaxStack();
56  * obj.push(x);
57  * int param_2 = obj.pop();
58  * int param_3 = obj.top();
59  * int param_4 = obj.peekMax();
60  * int param_5 = obj.popMax();
61  */

相关题目