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