阿里笔试330

复杂度O(n)

    请问有大佬明白为什么不ac吗。。。     input_val 和 n 分别是读取的list和int，assume没有重复值     input_val = sorted(input_val)     dp = [[0]*n]     dp[0] = 1     for i in range(1,n):         if input_val[i]==input_val[i-1]:             dp[i] = dp[i-1]+1         else:             dp[i] = 1     sum_val, count_val = 0,0     for i in range(len(dp)):         sum_val += dp[i]*input_val[i]         count_val += dp[i]     print (sum_val/count_val)

楼上大佬单调栈解法太强了 能不能帮忙看看我的代码是否可行，应该是O(nlogn)的复杂度。 dp[i]表示 以i为结尾的子序列的最大值的和 const int maxn = 1e5+7; typedef long long ll; int pos[maxn]; int val[maxn*10]; ll dp[maxn*10]; int max_pos(int s, int e) {     if(s > e) return -1;     if(s == e) return pos[s];     int mid = s + (e-s)/2;     int l = max_pos(s,mid);     int r = max_pos(mid+1,e);     return l > r ? l : r; } int main() {     int n;     while(~scanf("%d",&n)) {         int mx = -1;         for(int i = 0;i < n;i ++) {             scanf("%d",val+i);             mx = max(mx,val[i]);         }         double sum = 0;         memset(pos,-1,sizeof(pos));         for(int i = 0;i < n;i ++) {             int p = max_pos(val[i]+1,mx);             pos[val[i]] = i;             if(p == -1) dp[i] = val[i] * 1LL * (i-p);             else dp[i] = dp[p] + val[i] * 1LL * (i-p);             sum += dp[i];         }         sum = 2*sum / ((n+1) * n);         printf("%.6lf\n",sum);     }     return 0; }

我怎么感觉他不一定是升序呀！！！ public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);         int n = scanner.nextInt();         int[] arr = new int[n];         for (int i = 0; i < n; i++) {             arr[i] = scanner.nextInt();         }         scanner.close();         int[][] dp = new int[n][2];         for (int i = 0; i < n; i++) {             if (i > 0 && arr[i] > arr[i - 1]) {                 dp[i][0] = dp[i - 1][0] + 1;             }         }         for (int i = n - 1; i >= 0; i--) {             if (i < n - 1 && arr[i] > arr[i + 1]) {                 dp[i][1] = dp[i + 1][1] + 1;             }         }         int sum = 0;         int count = 0;         for (int i = 0; i < n; i++) {             sum += (dp[i][0] + 1 + dp[i][1] + dp[i][0] * dp[i][1]) * arr[i];             count += dp[i][0] + 1 + dp[i][1] + dp[i][0] * dp[i][1];         }         float result = sum / (float) count;         System.out.printf("%.6f", result);     }

第一题不会思路很清晰吗