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