2016 - Maximum Difference Between Increasing Elements

info

• 문제 보기: 2016 - Maximum Difference Between Increasing Elements
• 소요 시간: 7분 11초
• 풀이 언어: java
• 체감 난이도: 2️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

그리디

풀이 코드

info

• 메모리: 42140 KB
• 시간: 0 ms

class Solution {
    public int maximumDifference(int[] nums) {
        // init w/ -1
        // greedy w/ reverse iteration
        int ans = -1;
        int mx = nums[nums.length-1];
        for (int i = nums.length-2; -1 < i; --i) {
            int n = nums[i];
            if (n < mx)
                ans = mx-n < ans ? ans : mx-n;
            mx = mx < n ? n : mx;
        }

        return ans;
    }
}

풀이 해설

거꾸로 순회하며 diff를 구하면 되는 문제이다.

121 - Best Time to Buy and Sell Stock 문제와 매우 유사하며

백준 11501번 주식 문제와도 상당히 유사한

아주 전형적인 그리디 유형이다.

discussion에 있는 이 짤이 모든 설명을 대신하는듯.

메모

• Math.max 쓰면 1ms 됨... 확실히 메소드가 느림.
• 쉬운 편이나, 발상이 안되면 못 풀기 때문에 그리디 감 떨어지지 않게 자주 확인하기