100% java O(n) solution | easy understand
Explanation:\nFor condition1, we need to prepare two array which indicates the left max element and right minimum element. To generate this two array we will co
Explanation:\nFor condition1, we need to prepare two array which indicates the left max element and right minimum element. To generate this two array we will cost O(n) complexity.\nThen we just need one loop to get answer.\nHope it helps :)\n\n```java\n// AC: Runtime: 4 ms, faster than 100.00% of Java online submissions for Sum of Beauty in the Array.\n// Memory Usage: 55.5 MB, less than 83.33% of Java online submissions for Sum of Beauty in the Array.\n// .\n// T:O(n), S:O(n)\n// \nclass Solution {\n    public int sumOfBeauties(int[] nums) {\n        int size = nums.length, ret = 0;\n        int[] leftMax = new int[size], rightMin = new int[size];\n        int curLeftMax = nums[0];\n        for (int i = 1; i < size; i++) {\n            leftMax[i] = curLeftMax;\n            if (nums[i] > curLeftMax) {\n                curLeftMax = nums[i];\n            }\n        }\n        int curRightMin = nums[size - 1];\n        for (int i = size - 2; i >= 0; i--) {\n            rightMin[i] = curRightMin;\n            if (nums[i] < curRightMin) {\n                curRightMin = nums[i];\n            }\n        }\n\n        for (int i = 1; i < size - 1; i++) {\n            if (nums[i] > leftMax[i] && nums[i] < rightMin[i]) {\n                ret += 2;\n            } else if (nums[i] > nums[i - 1] && nums[i] < nums[i + 1]) {\n                ret += 1;\n            }\n        }\n\n        return ret;\n    }\n}\n```
['Array', 'Java']