일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- DWG
- shiba
- Decorator
- Convert Sorted List to Binary Search Tree
- Generator
- concurrency
- Class
- attribute
- 30. Substring with Concatenation of All Words
- Regular Expression
- kaggle
- Protocol
- Substring with Concatenation of All Words
- Python Code
- Python
- 43. Multiply Strings
- 시바견
- iterator
- Python Implementation
- 밴픽
- 운영체제
- 파이썬
- LeetCode
- data science
- 컴퓨터의 구조
- 프로그래머스
- t1
- 315. Count of Smaller Numbers After Self
- 715. Range Module
- 109. Convert Sorted List to Binary Search Tree
Archives
- Today
- Total
목록Largest Rectangle in Histogram (1)
Scribbling
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bdKU8d/btrgQAKVYKG/fGCNjmEUSJpkB8VRFSDak1/img.png)
문제 링크: https://leetcode.com/problems/largest-rectangle-in-histogram/ O(N)만에 푸는 방법을 떠올리는 것은 매우 어렵다. 이 문제를 O(N)에 풀 수 있는 방법은 monotonic stack을 이용하는 것이다. Monotonic Stack이란 stack을 쌓되 stack 내부가 오름차순 혹은 내림차순으로 정렬되도록 쌓는 것이다. 이 문제에서 Monotonic Stack이 사용되는 이유는 다음과 같다. 왼쪽에서부터 오른쪽으로 가면서 블록이 하나씩 추가된다고 고려했을 때, 이전에 추가된 블록에 비해 현재 블록의 높이가 작다면, 이전 블록의 높이가 직사각형의 최대 높이가 된다. 아래 그림에서 높이 2의 블록 차례가 오면, 높이 5와 높이 6의 블록은 더 ..
Computer Science/Coding Test
2021. 10. 4. 16:43