aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--design_stack_increment_op.c64
-rw-r--r--design_stack_increment_op.py61
2 files changed, 125 insertions, 0 deletions
diff --git a/design_stack_increment_op.c b/design_stack_increment_op.c
new file mode 100644
index 0000000..fbab1f4
--- /dev/null
+++ b/design_stack_increment_op.c
@@ -0,0 +1,64 @@
+// 1381. Design a Stack With Increment Operation
+#include "leetcode.h"
+
+/*
+ * design a stack that supports increment operations on its elements. implement
+ * the function increment that increments the bottom 'k' elements of the stack
+ * by 'val' if there are less than 'k' elements in the stack, increment all the
+ * elements in the stack
+ */
+
+typedef struct {
+ int *data;
+ int idx;
+ int size;
+} CustomStack;
+
+CustomStack *customStackCreate(int maxSize) {
+ CustomStack *obj = malloc(sizeof(CustomStack));
+ obj->data = (int *)calloc(maxSize, sizeof(int));
+ obj->size = maxSize;
+ obj->idx = 0;
+ return obj;
+}
+
+void customStackPush(CustomStack *obj, int x) {
+ if (obj->idx == obj->size)
+ return;
+ obj->data[obj->idx] = x;
+ obj->idx++;
+}
+
+int customStackPop(CustomStack *obj) {
+ if (!(obj->idx))
+ return -1;
+ obj->idx--;
+ return obj->data[obj->idx];
+}
+
+void customStackIncrement(CustomStack *obj, int k, int val) {
+ int min = k < obj->idx ? k : obj->idx;
+ for (int i = 0; i < min; i++)
+ obj->data[i] += val;
+}
+
+void customStackFree(CustomStack *obj) {
+ free(obj->data);
+ free(obj);
+}
+
+int main() {
+ CustomStack *obj = customStackCreate(3);
+ customStackPush(obj, 1);
+ customStackPush(obj, 2);
+ printf("%d\n", customStackPop(obj)); // expect: 2
+ customStackPush(obj, 2);
+ customStackPush(obj, 3);
+ customStackPush(obj, 4);
+ customStackIncrement(obj, 5, 100);
+ printf("%d\n", customStackPop(obj)); // expect: 103
+ printf("%d\n", customStackPop(obj)); // expect: 202
+ printf("%d\n", customStackPop(obj)); // expect: 201
+ printf("%d\n", customStackPop(obj)); // expect: -1
+ customStackFree(obj);
+}
diff --git a/design_stack_increment_op.py b/design_stack_increment_op.py
new file mode 100644
index 0000000..e531a52
--- /dev/null
+++ b/design_stack_increment_op.py
@@ -0,0 +1,61 @@
+# 1381. Design a Stack With Increment Operation
+
+"""
+design a stack that supports increment operations on its elements. implement
+the function increment that increments the bottom 'k' elements of the stack
+by 'val' if there are less than 'k' elements in the stack, increment all the
+elements in the stack
+"""
+
+
+class CustomStack(object):
+ def __init__(self, maxSize):
+ """
+ :type maxSize: int
+ """
+ self.n = maxSize
+ self.stack = []
+ self.inc = []
+
+ def push(self, x):
+ """
+ :type x: int
+ :rtype: None
+ """
+ if len(self.inc) < self.n:
+ self.stack.append(x)
+ self.inc.append(0)
+
+ def pop(self):
+ """
+ :rtype: int
+ """
+ if not self.inc:
+ return -1
+ if len(self.inc) > 1:
+ self.inc[-2] += self.inc[-1]
+ return self.stack.pop() + self.inc.pop()
+
+ def increment(self, k, val):
+ """
+ :type k: int
+ :type val: int
+ :rtype: None
+ """
+ if self.inc:
+ self.inc[min(k, len(self.inc)) - 1] += val
+
+
+if __name__ == "__main__":
+ obj = CustomStack(3)
+ obj.push(1)
+ obj.push(2)
+ print(obj.pop())
+ obj.push(2)
+ obj.push(3)
+ obj.push(4)
+ obj.increment(5, 100)
+ print(obj.pop())
+ print(obj.pop())
+ print(obj.pop())
+ print(obj.pop())