[LeetCode] 496. Next Greater Element I

https://leetcode.com/problems/next-greater-element-i/

Next Greater Element I - LeetCode

Next Greater Element I

 

 

nums2 배열에 수들이 들어있다.

nums1 배열은 nums2의 부분집합인데, 배열의 순서가 조금 다르다.

Next Greater Element 란 배열에서 해당 수 보다 크고, 해당 수보다 index가 뒤에 있는 수중 가장 작은 수이다.

우리는 nums1 배열에 있는 수들의 nums2 상에서의 Next Greater Element를 찾아주면 된다.

 

풀이는 아래와 같다.

 

1. nums2 수 -> index 로 변환할 수 있게 map또는 배열 ids를 만든다.

2. Stack st를 하나 만든다.

3. nums2를 훑으며 nums2의 해당 수가 st 가장 위에 쌓인 수보다 큰지 비교한다.

4. st 가장 위에 쌓인 수보다 크다면 nums2에서 st 가장 위에 쌓인 수를 찾아 현재 훑고 있는 수로 변경한다.

5. st pop을 해주고, 다음 위에 있는 수를 비교하는 작업을 반복한다.

6. st이 비어있거나 nums2의 수가 작을 경우 nums2의 수를 st에 쌓는다.

=> 이 경우에는 st 는 자연스럽게 아래쪽에 가장큰수가, 위로갈수록 작은 수가 쌓이게 된다.

7. nums1을 훑으며 ids를 이용해 nums2와 비교하여 nums1[i] = nums2[ids[nums1[i]] 일 경우, 큰 수가 없는 것이므로 -1을, 다를 경우엔 그 수로 업데이트 해준다.

 

전체 풀이 코드

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        int ids[10005];
        for (int i=0; i<nums2.size(); i++) ids[nums2[i]] = i;
        stack<int> st;
        for (int i=0; i<nums2.size(); i++) {
            while (!st.empty() && nums2[st.top()]<nums2[i]) {
                nums2[st.top()] = nums2[i];
                st.pop();
            }
            st.push(i);
        }
        for (int i=0; i<nums1.size(); i++) {
            if (nums2[ids[nums1[i]]]==nums1[i]) nums1[i] = -1;
            else nums1[i] = nums2[ids[nums1[i]]];
        }
        return nums1;
    }
};