[Stack] daily-temperatures - LeetCode Swift

문제 : https://leetcode.com/problems/daily-temperatures/

Daily Temperatures - LeetCode

 

풀이방법 : monotonic stack

단조로운 스택이란 뜻으로 스택을 증가시키는 형태나 감소시키는 형태로 유지하는 것이 핵심이다.

단조로운 형태로 가다가 그 형태가 벗어나면 앞에 것을 하나씩 인덱스 차이를 구하며 제거한다.

1. 우선 배열전체를 도는 반복문을 만든다.
2. 스택에 한개씩 넣는데 새로운 것을 추가할 때 새로운 것과 스택의 마지막 원소와 비교한다.
3. 단조로운 형태에 어긋난다면 스택의 마지막 것을 제거한다.
4. 다시 스택의 마지막 것과 새로운 것을 비교하고 제거한다. 반복
5. 형태에 어긋나지 않는다면 계속 한개씩 추가한다.
6. 제거하는 것과 새로 추가하는 것 사이의 인덱스 차이를 구한다.

 

코드

import Foundation

class Solution {
    func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
        var stack: [Int] = []
        var result = [Int](repeating: 0, count: temperatures.count)
        
        for i in 0..<temperatures.count {
            while !stack.isEmpty && temperatures[i] > temperatures[stack.last!] {
                let index = stack.removeLast()
                result[index] = i - index
            }
            stack.append(i)
        }
         return result
    }
}

 

비교 

모노토닉 큐 : https://hongz-developer.tistory.com/105

[Queue] 배열 구간 최솟값/최댓값 구하기