| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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
- Python
- 43. Multiply Strings
- DWG
- Class
- Python Code
- 109. Convert Sorted List to Binary Search Tree
- Decorator
- t1
- kaggle
- Substring with Concatenation of All Words
- shiba
- data science
- Protocol
- 315. Count of Smaller Numbers After Self
- 시바견
- Python Implementation
- Convert Sorted List to Binary Search Tree
- Regular Expression
- 715. Range Module
- LeetCode
- 프로그래머스
- concurrency
- attribute
- 운영체제
- iterator
- 밴픽
- 파이썬
- Generator
- 컴퓨터의 구조
- 30. Substring with Concatenation of All Words
Archives
- Today
- Total
목록84. Largest Rectangle in Histogram (1)
Scribbling
LeetCode: 84. Largest Rectangle in Histogram
문제 링크: 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