1. 题目描述:
  2. 请你设计一个支持下述操作的栈。
  3. 实现自定义栈类 CustomStack
  4. CustomStack(int maxSize):用 maxSize 初始化对象,maxSize 是栈中最多能容纳的元素数量,栈在增长到 maxSize 之后则不支持 push 操作。
  5. void push(int x):如果栈还未增长到 maxSize ,就将 x 添加到栈顶。
  6. int pop():弹出栈顶元素,并返回栈顶的值,或栈为空时返回 -1
  7. void inc(int k, int val):栈底的 k 个元素的值都增加 val 。如果栈中元素总数小于 k ,则栈中的所有元素都增加 val
  8. 示例:
  9. 输入:
  10. ["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
  11. [[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
  12. 输出:
  13. [null,null,null,2,null,null,null,null,null,103,202,201,-1]
  14. 解释:
  15. CustomStack customStack = new CustomStack(3); // 栈是空的 []
  16. customStack.push(1); // 栈变为 [1]
  17. customStack.push(2); // 栈变为 [1, 2]
  18. customStack.pop(); // 返回 2 --> 返回栈顶值 2,栈变为 [1]
  19. customStack.push(2); // 栈变为 [1, 2]
  20. customStack.push(3); // 栈变为 [1, 2, 3]
  21. customStack.push(4); // 栈仍然是 [1, 2, 3],不能添加其他元素使栈大小变为 4
  22. customStack.increment(5, 100); // 栈变为 [101, 102, 103]
  23. customStack.increment(2, 100); // 栈变为 [201, 202, 103]
  24. customStack.pop(); // 返回 103 --> 返回栈顶值 103,栈变为 [201, 202]
  25. customStack.pop(); // 返回 202 --> 返回栈顶值 202,栈变为 [201]
  26. customStack.pop(); // 返回 201 --> 返回栈顶值 201,栈变为 []
  27. customStack.pop(); // 返回 -1 --> 栈为空,返回 -1
  28. 提示:
  29. 1 <= maxSize <= 1000
  30. 1 <= x <= 1000
  31. 1 <= k <= 1000
  32. 0 <= val <= 100
  33. 每种方法 incrementpush 以及 pop 分别最多调用 1000
  34. /**
  35. * @param {number} maxSize
  36. */
  37. var CustomStack = function (maxSize) {
  38. //TODO
  39. };
  40. /**
  41. * @param {number} x
  42. * @return {void}
  43. */
  44. CustomStack.prototype.push = function (x) {
  45. //TODO
  46. };
  47. /**
  48. * @return {number}
  49. */
  50. CustomStack.prototype.pop = function () {
  51. //TODO
  52. };
  53. /**
  54. * @param {number} k
  55. * @param {number} val
  56. * @return {void}
  57. */
  58. CustomStack.prototype.increment = function (k, val) {
  59. //TODO
  60. };

我的回答

  1. /**
  2. * @param {number} maxSize
  3. */
  4. var CustomStack = function (maxSize) {
  5. //TODO
  6. this.maxSize = maxSize
  7. this.pushTimes = 0
  8. this.incrementTimes = 0
  9. this.popTimes = 0
  10. this.stack = []
  11. this.step = 1000
  12. return this.stack
  13. };
  14. /**
  15. * @param {number} x
  16. * @return {void}
  17. */
  18. CustomStack.prototype.push = function (x) {
  19. //TODO
  20. if (this.stack.length > this.maxSize || this.pushTimes > this.step) {
  21. return
  22. }
  23. this.pushTimes++
  24. this.stack.push(x)
  25. };
  26. /**
  27. * @return {number}
  28. */
  29. CustomStack.prototype.pop = function () {
  30. //TODO
  31. if (this.stack.length > this.maxSize || this.popTimes > this.step) {
  32. return
  33. }
  34. this.popTimes++
  35. return this.stack.pop()
  36. };
  37. /**
  38. * @param {number} k
  39. * @param {number} val
  40. * @return {void}
  41. */
  42. CustomStack.prototype.increment = function (k, val) {
  43. //TODO
  44. if (this.stack.length > this.maxSize || this.incrementTimes > this.step) {
  45. return
  46. }
  47. this.incrementTimes++
  48. if (k >= this.stack.length) {
  49. this.stack = this.stack.map((item) => item + value)
  50. } else {
  51. this.stack = [this.stack.slice(0, k).map((item) => item + value), ...this.stack.slice(k+1) ]
  52. }
  53. };

参考回答

  1. /**
  2. @param {number} maxSize */
  3. var CustomStack = function (maxSize) { this.maxSize = maxSize; this.stack = []; };
  4. /**
  5. @param {number} x
  6. @return {void} */
  7. CustomStack.prototype.push = function (x) {
  8. if (this.stack.length >= this.maxSize) { return; }
  9. this.stack.push(x);
  10. };
  11. /**
  12. @return {number} */
  13. CustomStack.prototype.pop = function () {
  14. const length = this.stack.length;
  15. return length < 1 ? -1 : (this.stack[length - 1], this.stack.pop())
  16. };
  17. /**
  18. @param {number} k
  19. @param {number} val
  20. @return {void} */
  21. CustomStack.prototype.increment = function (k, val) {
  22. let len = Math.min(k, this.stack.length)
  23. for (let i = 0; i < len; i++) {
  24. this.stack[i] += val;
  25. }
  26. };
  27. //另一种办法:使用js数组模拟栈操作
  28. var CustomStack = function (maxSize) {
  29. this.maxSize = maxSize
  30. this.index = 0
  31. this.stack = new Array(maxSize)
  32. }
  33. CustomStack.prototype.push = function (x) {
  34. if (this.index === this.maxSize) { return }
  35. this.stack[this.index++] = x
  36. }
  37. CustomStack.prototype.pop = function () {
  38. if (this.index === 0) {
  39. return -1
  40. }
  41. return this.stack[--this.index]
  42. }
  43. CustomStack.prototype.increment = function (k, val) {
  44. const l = this.index < k ? this.index : k
  45. for (let i = 0; i < l; i++) {
  46. this.stack[i] = this.stack[i] + val
  47. }
  48. }