[Algorithm Challenge] Design a stack that supports incremental operations (including parsing and source code)

O

(

n

)

O(n)

O(n), then the time complexity of incrementing the k elements at the end of the linked list is

O

(

k

)

O(k)

O(k), so the total time complexity of the incremental operation is

O

(

n

+

k

)

O(n + k)

O(n + k).

Complexity analysis

• Time complexity: push and pop are

  O

  (

  1

  )

  O(1)

  O(1), inc is

  O

  (

  n

  +

  k

  )

  O(n + k)

  O(n + k).

• Space complexity:

  O

  (

  m

  a

  x

  S

  i

  z

  e

  )

  O(maxSize)

  O(maxSize).

Code

JavaScript Code

/**
 * @param {number} maxSize
 */
var CustomStack = function (maxSize) {<!-- -->
    this.list = [];
    this.maxSize = maxSize;
};

/**
 * @param {number} x
 * @return {void}
 */
CustomStack.prototype.push = function (x) {<!-- -->
    if (this.list.length <this.maxSize) {<!-- -->
        this.list.push(x);
    }
};

/**
 * @return {number}
 */
CustomStack.prototype.pop = function () {<!-- -->
    const item = this.list.pop();
    return item === void 0 ? -1 : item;
};

/**
 * @param {number}k
 * @param {number} val
 * @return {void}
 */
CustomStack.prototype.increment = function (k, val) {<!-- -->
    for (let i = 0; i < k & amp; & amp; i <this.list.length; i + + ) {<!-- -->
        this.list[i] + = val;
    }
};

/**
 * Your CustomStack object will be instantiated and called as such:
 * var obj = new CustomStack(maxSize)
 * obj.push(x)
 * var param_2 = obj.pop()
 * obj.increment(k,val)
 */

Python Code

class CustomStack(object):

    def __init__(self, maxSize):
        """
        :type maxSize: int
        """
        self.list = []
        self.maxSize = maxSize

    def size(self):
        return len(self.list)


    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        if self.size() < self.maxSize:
            self.list.append(x)


    def pop(self):
        """
        :rtype: int
        """
        return -1 if self.size() == 0 else self.list.pop()


    def increment(self, k, val):
        """
        :type k: int
        :type val: int
        :rtype: None
        """
        size = k if k < self.size() else self.size()
        for i in range(0, size):
            self.list[i] + = val



# Your CustomStack object will be instantiated and called as such:
# obj = CustomStack(maxSize)
# obj.push(x)
# param_2 = obj.pop()
# obj.increment(k,val)

Method 2: Exchange space for time

In fact, we only care about the value of the element when popping it off the stack, so during incremental operations, we don't need to update the elements in the stack. Instead, we use a hashMap to record the number of elements that need to be added. When popping off the stack, check whether the subscript of the current element is recorded in the hashMap. If so, add the increment before popping it off the stack. This way we get the time complexity

O

(

1

)

O(1)

O(1) incremental operation, but the price is extra

O

(

N

)

O(N)

O(N) space.

Illustration

Complexity analysis

• Time complexity: push, pop and inc are all

  O

  (

  1

  )

  O(1)

  O(1).

• Space complexity:

  O

  (

  m

  a

  x

  S

  i

  z

  e

  )

  O(maxSize)

  O(maxSize), the space of the simulated stack array and hash table is

  O

  (

  m

  a

  x

  S

  i

  z

  e

  )

  O(maxSize)

  O(maxSize).

Code

JavaScript Code

/**
 * @param {number} maxSize
 */
var CustomStack = function (maxSize) {<!-- -->
    this.list = [];
    this.maxSize = maxSize;
    this.hashMap = {<!-- -->};
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
CustomStack.prototype._setInc = function (key, value) {<!-- -->
    if (!(key in this.hashMap)) {<!-- -->
        this.hashMap[key] = 0;
    }
    this.hashMap[key] + = value;
};

/**
 * @param {number} key
 * @return {number}
 */
CustomStack.prototype._getInc = function (key) {<!-- -->
    return this.hashMap[key] || 0;
};

/**
 * @return {number}
 */
CustomStack.prototype._size = function () {<!-- -->
    return this.list.length;
};

/**
 * @param {number} x
 * @return {void}
 */
CustomStack.prototype.push = function (x) {<!-- -->
    if (this._size() <this.maxSize) {<!-- -->
        this.list.push(x);
    }
};

/**
 * @return {number}
 */
CustomStack.prototype.pop = function () {<!-- -->
    const top = this._size() - 1;
    const inc = this._getInc(top);

    let item = this.list.pop();
    if (item === void 0) {<!-- -->
        return -1;
    }

    item + = inc;
    const newTop = top - 1;
    this._setInc(newTop, inc);
    this.hashMap[top] = 0;
    return item;
};

/**
 * @param {number}k
 * @param {number} val
 * @return {void}
 */
CustomStack.prototype.increment = function (k, val) {<!-- -->
    const size = this._size();
    k = k < size ? k - 1 : size - 1;
    this._setInc(k, val);
};

/**
 * Your CustomStack object will be instantiated and called as such:
 * var obj = new CustomStack(maxSize)
 * obj.push(x)
 * var param_2 = obj.pop()
 * obj.increment(k,val)
 */

Summary

The above is the entire content of this article. I hope it will be helpful to you and solve the problem of designing a stack that supports incremental operations.

If you like this article, please be sure to like, collect, comment, and forward it, it will be of great help to me. It would also be great to buy me a glass of iced Coke!

It has been completed, please continue to pay attention. See you next time~