力扣1381:设计一个支持增量操作的栈

请你设计一个支持对其元素举行增量操作的栈。
实现自定义栈类 CustomStack ：

• CustomStack(int maxSize)：用 maxSize 初始化对象，maxSize 是栈中最多能容纳的元素数目。
  
• void push(int x)：假如栈还未增长到 maxSize ，就将 x 添加到栈顶。
  
• int pop()：弹出栈顶元素，并返回栈顶的值，或栈为空时返回 -1 。
  
• void inc(int k, int val)：栈底的 k 个元素的值都增加 val 。假如栈中元素总数小于 k ，则栈中的所有元素都增加 val 。
  

示例：

1. <strong>输入：</strong>
2. ["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
3. [[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
4. <strong>输出：</strong>
5. [null,null,null,2,null,null,null,null,null,103,202,201,-1]
6. <strong>解释：</strong>
7. CustomStack stk = new CustomStack(3); // 栈是空的 []
8. stk.push(1);                          // 栈变为 [1]
9. stk.push(2);                          // 栈变为 [1, 2]
10. stk.pop();                            // 返回 2 --> 返回栈顶值 2，栈变为 [1]
11. stk.push(2);                          // 栈变为 [1, 2]
12. stk.push(3);                          // 栈变为 [1, 2, 3]
13. stk.push(4);                          // 栈仍然是 [1, 2, 3]，不能添加其他元素使栈大小变为 4
14. stk.increment(5, 100);                // 栈变为 [101, 102, 103]
15. stk.increment(2, 100);                // 栈变为 [201, 202, 103]
16. stk.pop();                            // 返回 103 --> 返回栈顶值 103，栈变为 [201, 202]
17. stk.pop();                            // 返回 202 --> 返回栈顶值 202，栈变为 [201]
18. stk.pop();                            // 返回 201 --> 返回栈顶值 201，栈变为 []
19. stk.pop();                            // 返回 -1 --> 栈为空，返回 -1

复制代码

代码：

1. typedef struct {
2.     int* stack;  // 用于存储栈中元素的整数指针
3.     int maxSize; // 栈的最大容量
4.     int top;     // 指示栈顶位置的整数
5. } CustomStack;
7. // 创建一个自定义栈，参数 maxSize 为栈的最大容量
8. CustomStack* customStackCreate(int maxSize) {
9.     CustomStack* obj = (CustomStack*)malloc(sizeof(CustomStack));
10.     obj->maxSize = maxSize;
11.     obj->stack = (int*)malloc(sizeof(int) * (maxSize + 1));
12.     memset(obj->stack, 0, sizeof(obj->stack));
13.     obj->top = -1;
14.     return obj;
15. }
17. // 将整数 x 压入栈中，若栈已满则不进行操作
18. void customStackPush(CustomStack* obj, int x) {
19.     if (obj->top  == obj->maxSize-1) {
20.         return;
21.     }
22.     obj->top++;
23.     obj->stack[obj->top] = x;
24. }
26. // 弹出栈顶元素，若栈为空则返回 -1
27. int customStackPop(CustomStack* obj) {
28.     if (obj->top == -1) {
29.         return -1;
30.     }
31.     int ans = obj->stack[obj->top];
32.     obj->top--;
33.     return ans;
34. }
36. // 对栈中前 k 个元素增加指定值 val，如果 k 大于栈中实际元素个数则调整 k 为实际元素个数
37. void customStackIncrement(CustomStack* obj, int k, int val) {
38.     if (obj->top == -1) {
39.         return;
40.     }
41.     if (k > obj->top + 1) {
42.         k = obj->top + 1;
43.     }
44.     for (int i = 0; i < k; i++) {
45.         obj->stack[i] += val;
46.     }
47. }
49. void customStackFree(CustomStack* obj) {
50.     free(obj->stack);
51.     free(obj);
52. }
54. /**
55. * Your CustomStack struct will be instantiated and called as such:
56. * CustomStack* obj = customStackCreate(maxSize);
57. * customStackPush(obj, x);
59. * int param_2 = customStackPop(obj);
61. * customStackIncrement(obj, k, val);
63. * customStackFree(obj);
64. */

复制代码

时间复杂度O（n）；空间复杂度O（n）



免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。