arrays - 计算从该索引开始的连续子数组

Question

我有一个数组A并且想要一个B相同大小的数组 A 其中B[i]表示连续子数组的长度A[i]以其中所有元素小于或等于A[i]

例子

A={1,3,4,2,4,5,1,6} 

输出

B={1,1,3,1,1,2,1,1} 

解释 ：

因为A[2]=4有一个带有元素的子数组{4,2,4}，因为A[5]=5有一个子数组，{5,1}因为A[7]=6有子数组{6}

Answer 1

You can apply below algorithm to get the answer for your problem:-

Array B =[]; //initialize blank array
for (int i=0; i< A.length(); i++)
{
    j=i;
    length=1;
    while(i< A.length()-1)
    {
        j++;
        if(A[j]<=A[i])
            length++;
        else
            break;
    }
B[i]= length;
}

Print B // This will give you the similar array as of Array "A". 

Answer 2

复杂度：O(n)

#include <iostream>
#include <fstream>
using namespace std;

#define max 10000

int main(int argc, const char * argv[]) {

    ifstream input("/Users/appleuser/Documents/Developer/xcode projects/SubArrayCount/SubArrayCount/input.in");

    int n, arr[max], after[max]={0};
    input >> n;
    for (int i=0; i<n; i++)
        input >> arr[i];

    for (int i=n-1;i>=0;i--)
        for (int j=i+1;j<n&&arr[j]<=arr[i];j+=after[j]+1)
        {
            if (arr[j]==arr[i])
            {
                after[i]++;
                break;
            }
            after[i]+=after[j]+1;
        }


    for (int i=0; i<n; i++)
        cout << after [i] << " ";
    cout << endl;

    return 0;
}