C++ Simple Solution


  • 0

    Inspired by @dong-wang-1694 's Solution for Question : Candy

    I remove concise from the title of this post since I find other posts' code is much straightforward and concise. Hope my post can help you solve this question

    Thought:
    We need handle every "Mountain" individually. Use [start, peak_index, i] to represent previous mountain.
    Every "mountain" should be arranged in this shape. Use peak_val to record current number.

            6
              5
                4
                  3
        2
      1
    
    class Solution {
    public:
        vector<int> findPermutation(string s) {
            int n = s.size(), start = 0, peak_index = 0, peak_val = 0;
            bool has_peak = false;
            vector<int> res(n + 1, 0);
            res[0] = 1;
            for (int i = 0; i < n; i++) {
                if (s[i] == 'I') {
                    if (has_peak) {
                        has_peak = false;
                        // handle previous peak [start, peak_index, i]
                        for (int j = start; j < peak_index; j++)
                            res[j] = ++peak_val;
                        for (int j = i; j >= peak_index; j--)
                            res[j] = ++peak_val;
                        start = i + 1;
                    }
                } else {
                    if (!has_peak) {
                        has_peak = true;
                        peak_index = i;
                    }
                }
            }
            // handle last mountain
            for (int j = start; j < (has_peak ? peak_index : n + 1); j++)
                res[j] = ++peak_val;
            for (int j = n; j >= (has_peak ? peak_index : n + 1); j--)
                res[j] = ++peak_val;
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.