일일 온도 Leetcode 솔루션

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 ByteDance C3 사물인터넷 시스코 드 쇼 Facebook 구글 Microsoft 신탁 페이팔 세일즈 포스 Twitter 동네 짱 비자, Zillow
배열 스택 Tik의 톡조회수 59

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 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 솔루션:

시간 복잡성

위 코드의 시간 복잡성은 의 위에).

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. 의 위에).

 

균열 시스템 설계 인터뷰
Translate »