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.
Constraints:
1 <= maxSize <= 1000
1 <= x <= 1000
1 <= k <= 1000
0 <= val <= 100
- At most
1000
calls will be made to each method ofincrement
,push
andpop
each separately.
A:
Tricky的地方就是: 每次inc 只记录一个位置,然后每次退出一个位置的时候,把其值加到前一个上。
class CustomStack { public: CustomStack(int maxSize) { capacity = maxSize; IncVal = vector<int>(maxSize,0); } void push(int x) { if(values.size() >= capacity) return; values.push(x); } int pop() { if(values.empty()) return -1; int res = values.top()+IncVal[values.size()-1]; if(values.size() > 1){ IncVal[values.size()-2] += IncVal[values.size()-1]; } IncVal[values.size()-1] = 0; values.pop(); return res; } void increment(int k, int val) { if(values.size()>0 && k > 0){ IncVal[min(k-1,int(values.size()-1))] += val; } } private: stack<int> values; vector<int> IncVal; int capacity =0; }; /** * Your CustomStack object will be instantiated and called as such: * CustomStack* obj = new CustomStack(maxSize); * obj->push(x); * int param_2 = obj->pop(); * obj->increment(k,val); */
No comments:
Post a Comment