CY-Left

LeetCode基本功底

907. Sum of Subarray Minimums

907. Sum of Subarray Minimums

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

Since the answer may be large, return the answer modulo 10^9 + 7.

给出整型数组 A, 寻找所有子串中最小值的和 min(B), 其中 B 是 A 中所有连接子串。由于结果很大,最后结果对 10^9 + 7 取余

例子 1:

Input: [3,1,2,4]
Output: 17
解释: 所有的子串为 [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
最小值分别为 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  和为 17.

注意:

  1. 1 <= A.length <= 30000

  2. 1 <= A[i] <= 30000

class Solution {
public:
    int sumSubarrayMins(vector<int>& A) {
        int mod = 1000000007;
        queue<int> curSubstringMin;
        int sum = 0;
        int vectorSize = A.size();
        int preIndex = 0;
        for (int i=0; i<vectorSize; i++) {
            curSubstringMin.push(A[i]);
        }

        for (int i=1; i<=vectorSize; i++) {
            for(int j=0;j<vectorSize;j++){
                if( j+i< vectorSize ) {
                    ( A[j+i] > curSubstringMin.front() )
                    ? curSubstringMin.push(curSubstringMin.front())
                    : curSubstringMin.push(A[j+i]);
                    sum += curSubstringMin.front();
                    curSubstringMin.pop();
                }else {
                    sum += curSubstringMin.front();
                    curSubstringMin.pop();
                    break;
                }
            }
            sum %= mod;
        }
        return sum;
    }
};

结果超时

本文虽拙,却也系作者劳动,转载还请保留本文链接: http://cyleft.com/?p=895