Monotonic Stack 2문제, Intervals 1문제를 풀었다. Monotonic Stack은 스택 내부의 값이 단조 증가하거나, 단조 감소하는 요소를 가진 것을 나타낸다.
739. Daily Temperatures
일일 온도를 나타내는 정수 배열 temperatures가 주어졌을 때, answer[i]가 temperatures[i] 보다 더 따뜻한 날이 올 때까지 걸리는 일수인 배열 answer를 반환하라. 만약 더 따뜻한 날이 오지 않는다면 answer[i] = 0으로 둔다.
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Monotonic Stack 이라는 주제를 알지 못했기 때문에 😅 쉬운 문제였지만 풀지 못했던 것 같다(솔루션). 배열을 끝에서부터 순회한다. 스택에는 값이 아닌 인덱스가 들어있고, temperatures[i] 보다 작은 값이 없어야 한다. 그리고 스택에 빈 값이 없다면(=temperatures[i] 보다 큰 값이 있다면) answer[i]를 업데이트한다. 그리고 스택에 i를 추가한다.
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] ret = new int[n];
Stack<Integer> s = new Stack<>();
for(int i=n-1; i>=0; i--) {
while(!s.isEmpty() && temperatures[i] >= temperatures[s.peek()]) {
s.pop();
}
if (!s.isEmpty()) {
ret[i] = s.peek() - i;
}
s.push(i);
}
return ret;
}
}시간복잡도는 temperatures 배열을 순회하기 때문에 O(n), 공간복잡도는 스택에 배열의 인덱스를 저장하므로 O(n)이다.
901. Online Stock Span
StockSpanner 클래스를 구현하라:
- 생성자 구현
- int next(int price) 주어진 오늘의 주식 가격에 대해서 span을 리턴하는 함수
Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day.
The span of the stock's price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day.
For example, if the prices of the stock in the last four days is [7,2,1,2] and the price of the stock today is 2, then the span of today is 4 because starting from today, the price of the stock was less than or equal 2 for 4 consecutive days.
Also, if the prices of the stock in the last four days is [7,34,1,2] and the price of the stock today is 8, then the span of today is 3 because starting from today, the price of the stock was less than or equal 8 for 3 consecutive days.
Implement the StockSpanner class:
- StockSpanner() Initializes the object of the class.
- int next(int price) Returns the span of the stock's price given that today's price is price.
next 함수가 반환해야 하는 값에 대해서 이해하는 것이 중요하다. 위에서 든 예시처럼 지난 4일간 주식 가격이 [7, 2, 1, 2]였을 때, 오늘 가격이 2라면, 리턴해야 하는 값(span)은 오늘부터 가격이 2 또는 2 보다 작았던 날이 4일이었기 때문에 4가 된다. 다른 예로 [7, 34, 1, 2]이고 오늘 가격이 8이라면 next 함수가 리턴하는 값은 3이다.
스택에는 price와 price 보다 작거나 같은 값이 출현한 횟수가 배열로 저장되어 있다. 스택에 price 보다 작은 값이 있다면 pop하고 출현한 횟수에 더해준다. 그리고 스택에 오늘의 price와 합한 출현 횟수를 push 하고, 출현 횟수를 리턴한다.
class StockSpanner {
Stack<int[]> stack = new Stack<>();
public int next(int price) {
int ans = 1;
while (!stack.isEmpty() && stack.peek()[0] <= price) {
ans += stack.pop()[1];
}
stack.push(new int[] {price, ans});
return ans;
}
}next 함수안에 while문이 있긴 하지만 이 함수를 n번 실행한다고 했을 때 걸리는 평균 시간 복잡도는 O(1)이 된다. 왜냐하면 while문은 많아야 요소를 n번 pop 하기 때문이다. 그리고 스택이 최악의 경우 n개의 원소를 저장할 수 있으므로 공간 복잡도는 O(n)이 된다.
452. Minimum Number of Arrows to Burst Balloons
2차원 배열 points의 인자 points[i] = [x_start, x_end]로 풍선의 가로 직경을 나타낸다. 풍선의 y 좌표는 알 수 없다. 화살은 수직 방향으로 날릴 수 있다. 화살을 쏜 좌표값이 x_start와 x_end 사이에 있다면 풍선은 터진다. 화살은 무한히 날아가서 그 경로에 있는 모든 풍선을 터트릴 수 있다.
풍선 좌표가 들어있는 배열 points가 있을 때 모든 풍선을 터뜨리기 위해 필요한 최소한의 화살 수를 반환하라.
There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [x_start, x_end] denotes a balloon whose horizontal diameter stretches between x_start and x_end. You do not know the exact y-coordinates of the balloons.
Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with x_start and x_end is burst by an arrow shot at x if x_start <= x <= x_end. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.
Given the array points, return the minimum number of arrows that must be shot to burst all balloons.
풍선들의 겹치는 구간을 쏴야 최소한의 화살로 풍선을 모두 터뜨릴 수 있다. 그래서 풍선들끼리 겹치는 범위를 찾아서 그 구간을 저장해나가면, 배열에는 최종적으로 겹치지 않는 구간들이 남을 것이고, 그러면 배열의 크기가 필요한 화살이 개수가 될 것이다.
그래서 구간들이 서로 겹치는지 비교를 해야 하는데, 효과적으로 비교하기 위해서 배열을 정렬한다. 그리고 겹치는 구간을 구한다. 겹치는 구간이 있으면 겹치는 구간을 추가하고, 없으면 비교했던 두 구간을 리스트에 넣는다. 배열을 돌면서 반복한다.
class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length == 1) {
return 1;
}
Arrays.sort(points, (a, b) -> a[0] < b[0] ? -1 : 1);
List<int[]> arrows = new ArrayList<>();
int[] intersection = intersect(points[0], points[1]);
if (intersection != null) {
arrows.add(intersection);
} else {
arrows.add(points[0]);
arrows.add(points[1]);
}
for(int i=2; i<points.length; i++) {
int[] last = arrows.get(arrows.size()-1);
intersection = intersect(last, points[i]);
if (intersection == null) {
arrows.add(points[i]);
} else {
arrows.remove(arrows.size()-1);
arrows.add(intersection);
}
}
return arrows.size();
}
private int[] intersect(int[] point1, int[] point2) {
if (point1[1] >= point2[0]) {
return new int[]{point2[0], Math.min(point1[1], point2[1])};
}
return null;
}
}points 배열의 길이를 n이라고 할 때, 정렬할 때 O(nlogn)이 소요된다. 그리고 points를 순회하면서 겹치는 구간이 있는지 확인한다(O(n)). 따라서 시간 복잡도는 O(n + nlogn) = O(nlogn)이다.
공간 복잡도는 arrows 배열에 points를 저장하므로 O(n)이다.
