leetcode 1381

问题

Design a stack which supports the following operations.

Implement the CustomStack class:

  • CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.
  • void push(int x) Adds x to the top of the stack if the stack hasn’t reached the maxSize.
  • int pop() Pops and returns the top of stack or -1 if the stack is empty.
  • void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 of increment, push and pop each separately.

分析

思路1: 使用一个普通的栈表示正常的push和pop，使用一个树状数组来表示区间的增长。push时正常push。pop时加上树状数组上的延迟标记，并对延迟标记进行调整。时间复杂度push: O(1), pop() : O(logn), increment: O(logn).

思路2: 分析可知increment进行区间增常时，区间头总是0。因此可以另外使用一个inc数组进行延迟标记的，inc[i] 表示栈中前i个元素都应该加1。push时正常push。pop时加上inc[i]，并令inc[i-1] = inc[i]. increment 时对inc[i]进行负值。push: O(1), pop() : O(1), increment: O(1)。参考)

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// push: O(1), pop() : O(logn), increment: O(logn)
class CustomStack {
public:
    vector<int> s;
    vector<int> c;
    int size;
    int maxSize;

    inline int lowbit(int x) {
        return x&(-x);
    }

    int getSum(int index) {
        int i = index;
        int ret = 0;
        while (i >= 1) {
            ret += c[i];
            i -= lowbit(i);
        }
        return ret;
    }

    void add(int index, int val) {
        int i = index;
        while (i <= maxSize) {
            c[i] += val;
            i += lowbit(i);
        }
    }

    CustomStack(int maxSize) {
        this->maxSize = maxSize;
        size = 0;
        s.push_back(0);
        c = vector<int>(maxSize+2, 0);
    }
    
    void push(int x) {
        if (size >= maxSize)
            return;
        s.push_back(x);
        ++size;
    }
    
    int pop() {
        if (size == 0)
            return -1;
        int val = getSum(size);
        add(size, -val);
        add(size+1, -getSum(size+1));
        int ret = val+s.back();
        s.pop_back();
        --size;
        return ret;
    }
    
    void increment(int k, int val) {
        add(1, val);
        add(min(k, size)+1, -val);
    }
};

/**
 * 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);
 */

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class CustomStack {
public:
    stack<int> s;
    vector<int> inc;
    int n;
    CustomStack(int maxSize) {
        n = maxSize;
        inc = vector<int>(n, 0);
    }
    
    void push(int x) {
        if (s.size() < n)
            s.push(x);
    }
    
    int pop() {
        if (s.size() == 0)
            return -1;
        int i = s.size()-1;
        if (i-1 >= 0)
            inc[i-1] += inc[i];
        int ret = s.top()+inc[i];
        inc[i] = 0;
        s.pop();
        return ret;
    }
    
    void increment(int k, int val) {
        if (s.size() == 0 || k == 0)
            return;
        inc[min((int)s.size(), k)-1] += val;
    }
};

/**
 * 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);
 */