diff options
-rw-r--r-- | design_stack_increment_op.c | 64 | ||||
-rw-r--r-- | design_stack_increment_op.py | 61 |
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()) |