Java에서 단조로운 스택을 사용하는 방법

1. 다음으로 큰 요소

문제 설명

아이디어에 대한 자세한 설명

이 질문은 더 폭력적인 해결책을 사용합니다.

먼저 결과를 저장하기 위해 nums와 동일한 길이의 res 배열을 초기화하고 nums2[j] == nums[i]를 찾을 때까지 nums2에서 검색합니다. 그런 다음 nums2의 j부터 시작합니다. 그런 다음 nums[i]보다 큰 배열을 찾아 반환합니다. 찾을 수 없으면 -1을 반환합니다.

코드 및 결과

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] res = new int[m];
        for (int i = 0; i < m; ++i) {
            int j = 0;
            while (j < n && nums2[j] != nums1[i]) {
                ++j;
            }
            int k = j + 1;
            while (k < n && nums2[k] < nums2[j]) {
                ++k;
            }
            res[i] = k < n ? nums2[k] : -1;
        }
        return res;
    }
}

2.

문제 설명

아이디어에 대한 자세한 설명

이 질문 역시 비교적 폭력적인 방법을 사용하고 있습니다. 이전 질문과 동일합니다.

이중 루프, 분명히 이 방법은 시간 복잡도가 더 높습니다. 시간 복잡도가 낮은 방법도 여기에 제공됩니다.

단조로운 스택

우리가 유지하는 것은 결과 배열인 간격 배열입니다. 먼저 스택을 생성하고 스택이 비어 있는지 확인하고 비어 있지 않으면 스택에 직접 푸시합니다. 스택의 최상위 요소를 현재 요소와 비교합니다. 현재 요소가 현재 요소보다 크면 차이가 해당 결과 배열에 저장되고 현재 요소가 현재 요소보다 작으면 스택의 최상위 요소가 팝됩니다. 결과 배열은 스택에 푸시됩니다.

여기 애니메이션 링크가 있습니다. 애니메이션에서 단조로운 스택을 배우는 것이 좋습니다.

코드 및 결과

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        for(int i = 0 ; i < temperatures.length ; i++){
            int res = 0;
            for(int j = i+1 ; j < temperatures.length; j++){
                res++;
                if(temperatures[j] > temperatures[i]){
                    answer[i] = res;
                    break;
                } 
            }
        }
        return answer;
    }
}

3. 다음으로 큰 요소 II

문제 설명

자세한 아이디어

이 질문의 아이디어는 단조로운 스택입니다. . 이 질문에는 단조로운 스택을 사용해야 합니다.

원리는 두 번째 질문의 방법과 동일합니다. 루프에만 주의하세요. 코드에 직접 가셔서 잘 모르시면 두 번째 질문 영상을 보시고 이 내용을 보시면 됩니다.

코드 및 결과

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ret = new int[n];
        Arrays.fill(ret, -1);
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < n * 2 - 1; i++) {//最多循环一次，只需要2*n-1就够用了
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                ret[stack.pop()] = nums[i % n];
            }
            stack.push(i % n);//利用取模来进行循环也是一种常用的方法
        }
        return ret;
    }
}

위 내용은 Java에서 단조로운 스택을 사용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!