Stack
-
[LeetCode] Validate Binary Search Tree알고리즘 2019. 11. 27. 17:02
문제 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. Example 1: 2 / \ 1 3 Input: [2,1,3] Output: true..
-
[LeetCode] Binary Tree Inorder Traversal알고리즘 2019. 11. 26. 17:37
문제 Given a binary tree, return the inorder traversal of its nodes' values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively? Apporach Inorder traversal: 왼쪽 자식-> 자신 -> 오른쪽 자식 순으로 트리 탐색 Recursive로 풀면 직관적이고 함수 스택 말고 실제 stack을 활용해 반복문으로 풀 수도 있다. Code Recursive: https://github.com/chi3236/algorithm/blob/master/LeetCode_Binary..
-
[LeetCode] Largest Rectangle in Histogram알고리즘 2019. 11. 20. 18:05
문제 Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]. The largest rectangle is shown in the shaded area, which has area = 10 unit. Example: Input: [2,1,5,6,2,3] Output: 10 Approach i번째 막대에서 가장 큰 직사각형을 만드려면 i번째 막..
-
[LeetCode] Longest Valid Parentheses알고리즘 2019. 10. 9. 16:41
문제 Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. Example 1: Input: "(()" Output: 2 Explanation: The longest valid parentheses substring is "()" Example 2: Input: ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()" Approach 우선 Valid parentheses의 조건을 잘 생각해봐야한다. ')'가 나왔을 때 그 바로 전에 '(..