시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
또한 일일 온도 Leetcode 솔루션: 주어진 정수 배열을 나타냅니다. temperatures 일일 온도, 반환을 나타냅니다. 배열 answer 그렇게 answer[i] 이후에 기다려야 하는 일 수입니다. ith 기온이 더 올라가는 날. 이것이 가능한 미래의 날이 없다면, 다음을 유지하십시오. answer[i] == 0 대신.
예 1 :
입력:
온도 = [73,74,75,71,69,72,76,73]
출력:
[1,1,4,2,1,1,0,0]
설명 :
1일차의 경우 2일차, 즉 1일까지 기다려야 합니다.
2일차의 경우 3일차, 즉 1일까지 기다려야 합니다.
3일차에는 7일차, 즉 4일을 기다려야 합니다.
등등.
예 2 :
입력:
온도 = [30,40,50,60]
출력:
[1,1,1,0]
설명 :
1일차의 경우 2일차, 즉 1일까지 기다려야 합니다.
2일차의 경우 3일차, 즉 1일까지 기다려야 합니다.
3일차의 경우 4일차, 즉 1일까지 기다려야 합니다.
등등.
예 3 :
입력:
온도 = [30,60,90]
출력:
[1,1,0]
설명 :
1일차의 경우 2일차, 즉 1일까지 기다려야 합니다.
2일차의 경우 3일차, 즉 1일까지 기다려야 합니다.
3일차에는 0일을 기다릴 필요가 없습니다.
접근
아이디어 :
그런 다음 온도 배열을 탐색하고 모든 인덱스 i에 대해 다음 작업을 수행합니다.
- 스택이 비어 있지 않으면 현재 스택의 맨 위에 있는 인덱스를 가변 인덱스에 저장합니다. 만약 온도가
ith day는 에서보다 엄격하게 큽니다.indexth day, 그런 다음 현재 날짜보다 더 높은 온도를 발견했기 때문에 index-i 일로 ans[i]를 업데이트합니다. 인덱스는 스택에서 제거됩니다. 즉, 스택에서 팝 작업을 수행합니다.
- 위의 단계는 다음 온도까지 계속됩니다.
ith 일보다 엄격하게 낮습니다.indexth 일. - 위의 단계가 계속되면 i보다 작은 위치에서 as 배열을 업데이트합니다.
- 결국 현재 반복 i를 스택에 푸시합니다.
마지막으로 현재 날짜에 더 높은 온도를 얻기 위해 기다려야 하는 일 수와 함께 응답 배열을 얻습니다.
암호
일일 온도 Leetcode C++ 솔루션:
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n=temperatures.size();
vector<int>ans(n,0);
stack<int>st;
for(int i=0;i<n;i++)
{
while(!st.empty() && temperatures[i]>temperatures[st.top()])
{
int index=st.top();
st.pop();
ans[index]=i-index;
}
st.push(i);
}
return ans;
}
};
일일 온도 Leetcode Java 솔루션:
class Solution {
public int[] dailyTemperatures(int[] temperatures){
Stack<Integer> st= new Stack();
int n=temperatures.length;
int ans[]=new int[n];
for(int i=0;i<n;i++)
{
while(st.size()>0 && temperatures[i]>temperatures[st.peek()])
ans[st.peek()]=i-st.pop();
st.push(i);
}
return ans;
}
}
일일 온도 Leetcode Python 솔루션:
class Solution(object):
def dailyTemperatures(self, temperatures):
n = len(temperatures)
ans = [0 for _ in range(n)]
st = []
for i in range(0, n):
while (len(st)>0) and temperatures[i]> temperatures[st[len(st)-1]]:
index = st[len(st)-1]
st.pop()
ans[index] = i-index
st.append(i)
return list(ans)
일일 온도에 대한 복잡성 분석 Leetcode 솔루션:
시간 복잡성
위 코드의 시간 복잡성은 의 위에).
공간 복잡성
위 코드의 공간 복잡성은 다음과 같습니다. 의 위에).
