Design a stack which supports the following operations.
Implement the CustomStack
class:
-
CustomStack(int maxSize)
Initializes the object withmaxSize
which is the maximum number of elements in the stack or do nothing if the stack reached themaxSize
. -
void push(int x)
Addsx
to the top of the stack if the stack hasn't reached themaxSize
. -
int pop()
Pops and returns the top of stack or -1 if the stack is empty. -
void inc(int k, int val)
Increments the bottomk
elements of the stack byval
. If there are less thank
elements in the stack, just increment all the elements in the stack.
Example 1:
Input ["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"] [[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]] Output [null,null,null,2,null,null,null,null,null,103,202,201,-1] Explanation CustomStack customStack = new CustomStack(3); // Stack is Empty [] customStack.push(1); // stack becomes [1] customStack.push(2); // stack becomes [1, 2] customStack.pop(); // return 2 --> Return top of the stack 2, stack becomes [1] customStack.push(2); // stack becomes [1, 2] customStack.push(3); // stack becomes [1, 2, 3] customStack.push(4); // stack still [1, 2, 3], Don't add another elements as size is 4 customStack.increment(5, 100); // stack becomes [101, 102, 103] customStack.increment(2, 100); // stack becomes [201, 202, 103] customStack.pop(); // return 103 --> Return top of the stack 103, stack becomes [201, 202] customStack.pop(); // return 202 --> Return top of the stack 102, stack becomes [201] customStack.pop(); // return 201 --> Return top of the stack 101, stack becomes [] customStack.pop(); // return -1 --> Stack is empty return -1.
分析:https://leetcode.com/problems/design-a-stack-with-increment-operation/discuss/539716/JavaC%2B%2BPython-Lazy-increment-O(1)
Use an additional array to record the increment value. inc[i]
means for all elements stack[0] ~ stack[i]
,we should plus inc[i]
when popped from the stack. Then inc[i-1]+=inc[i]
, so that we can accumulate the increment inc[i]
for the bottom elements and the following pop
s.
1 class CustomStack { 2 int n; 3 int[] inc; 4 Stack<Integer> stack; 5 public CustomStack(int maxSize) { 6 n = maxSize; 7 inc = new int[n]; 8 stack = new Stack<>(); 9 } 10 11 public void push(int x) { 12 if (stack.size() < n) { 13 stack.push(x); 14 } 15 } 16 17 public int pop() { 18 int i = stack.size() - 1; 19 if (i < 0) return -1; 20 if (i > 0) inc[i - 1] += inc[i]; 21 int res = stack.pop() + inc[i]; 22 inc[i] = 0; 23 return res; 24 } 25 26 public void increment(int k, int val) { 27 int i = Math.min(k, stack.size()) - 1; 28 if (i >= 0) { 29 inc[i] += val; 30 } 31 } 32 } 33 34 /** 35 * Your CustomStack object will be instantiated and called as such: 36 * CustomStack obj = new CustomStack(maxSize); 37 * obj.push(x); 38 * int param_2 = obj.pop(); 39 * obj.increment(k,val); 40 */