1381. Design a Stack With Increment Operation
Design a stack which supports the following operations.
Implement the CustomStack class:
CustomStack(int maxSize)Initializes the object withmaxSizewhich is the maximum number of elements in the stack or do nothing if the stack reached themaxSize.void push(int x)Addsxto 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 bottomkelements of the stack byval. If there are less thankelements 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 <= 10001 <= x <= 10001 <= k <= 10000 <= val <= 100- At most
1000calls will be made to each method ofincrement,pushandpopeach separately.
设计一个栈Stack的数据结构，简单题，使用vector模拟。完整代码如下：
class CustomStack {
private:
vector<int> container;
int msz;
public:
CustomStack(int maxSize) {
msz = maxSize;
}
void push(int x) {
if (container.size() < msz) {
container.push_back(x);
}
}
int pop() {
if (container.size() > 0) {
int val = container[container.size() - 1];
container.pop_back();
return val;
}
else {
return -1;
}
}
void increment(int k, int val) {
for (int i = 0; i < k&&i < container.size(); ++i) {
container[i] += val;
}
}
};本代码提交AC，用时40MS。
