An application at Amazon is deployed on n servers connected linearly. The vulnerability of the i-th server is given by vulnerability[i]. The system vulnerability of a contiguous segment of servers is defined as the number of servers in the segment × the maximum vulnerability of the segment. Given the vulnerability array, find the sum of system vulnerabilities of all the segments (subsegments) of the servers. Since the answer can be very large, report it modulo 10⁹ + 7.
Constraints
1 ≤ n ≤ 10⁵1 ≤ vulnerability[i] ≤ 10⁹
Example
vulnerability = [3, 1, 4]
answer = 34| Subsegment | servers | max | system vuln |
|---|---|---|---|
| [3] | 1 | 3 | 3 |
| [3,1] | 2 | 3 | 6 |
| [3,1,4] | 3 | 4 | 12 |
| [1] | 1 | 1 | 1 |
| [1,4] | 2 | 4 | 8 |
| [4] | 1 | 4 | 4 |
解法
单调栈。对每个 i 找左侧严格更大、右侧 ≥ 的最近下标，设 l = i - left[i]、r = right[i] - i。v[i] 作为最大值时对所有子段的贡献为 v[i] · l · r · (l + r) / 2。复杂度 O(n)。
def getSystemVulnerability(vulnerability):
MOD = 10**9 + 7
INV2 = pow(2, MOD - 2, MOD)
n = len(vulnerability)
left = [-1] * n
stack = []
for i in range(n):
while stack and vulnerability[stack[-1]] <= vulnerability[i]:
stack.pop()
left[i] = stack[-1] if stack else -1
stack.append(i)
right = [n] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and vulnerability[stack[-1]] < vulnerability[i]:
stack.pop()
right[i] = stack[-1] if stack else n
stack.append(i)
ans = 0
for i in range(n):
l = i - left[i]
r = right[i] - i
contrib = vulnerability[i] * l % MOD * r % MOD * (l + r) % MOD * INV2 % MOD
ans = (ans + contrib) % MOD
return ansimport java.util.*;
class Solution {
public int getSystemVulnerability(List<Integer> vulnerability) {
final long MOD = 1_000_000_007L;
final long INV2 = (MOD + 1) / 2;
int n = vulnerability.size();
int[] v = new int[n];
for (int i = 0; i < n; i++) v[i] = vulnerability.get(i);
int[] left = new int[n];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && v[stack.peek()] <= v[i]) stack.pop();
left[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(i);
}
int[] right = new int[n];
stack.clear();
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && v[stack.peek()] < v[i]) stack.pop();
right[i] = stack.isEmpty() ? n : stack.peek();
stack.push(i);
}
long ans = 0;
for (int i = 0; i < n; i++) {
long l = i - left[i];
long r = right[i] - i;
long contrib = v[i] % MOD * l % MOD * r % MOD * ((l + r) % MOD) % MOD * INV2 % MOD;
ans = (ans + contrib) % MOD;
}
return (int) ans;
}
}#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
int getSystemVulnerability(vector<int>& vulnerability) {
const long long MOD = 1'000'000'007LL;
const long long INV2 = (MOD + 1) / 2;
int n = vulnerability.size();
vector<int> left(n), right(n);
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && vulnerability[st.top()] <= vulnerability[i]) st.pop();
left[i] = st.empty() ? -1 : st.top();
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && vulnerability[st.top()] < vulnerability[i]) st.pop();
right[i] = st.empty() ? n : st.top();
st.push(i);
}
long long ans = 0;
for (int i = 0; i < n; i++) {
long long l = i - left[i];
long long r = right[i] - i;
long long contrib = (long long)vulnerability[i] % MOD * l % MOD * r % MOD * ((l + r) % MOD) % MOD * INV2 % MOD;
ans = (ans + contrib) % MOD;
}
return (int) ans;
}
};Amazon Technical Academy (ATA) provides on-demand technical training to current Amazon employees looking to broaden their skill sets. ATA has admitted a group of n prospective trainees with varying skill levels. To better accommodate the trainees, ATA has decided to create classes tailored to the skill levels. A placement examination will return a skill level that will be used to group the trainees into classes, where levels[i] represents the skill level of trainee i. All trainees within a class must have a skill level within maxSpread of one another. Determine the minimum number of classes that must be formed.
Constraints
1 ≤ n ≤ 10⁵1 ≤ levels[i] ≤ 10⁹for everyi(where0 ≤ i ≤ n-1)0 ≤ maxSpread ≤ 10⁹
Example
n = 4
levels = [4, 8, 1, 7]
maxSpread = 3
answer = 2解法
排序后贪心：当前元素超过 start + maxSpread 时开一组新班。复杂度 O(n log n)。
def groupStudents(levels, maxSpread):
levels.sort()
classes = 1
start = levels[0]
for x in levels:
if x - start > maxSpread:
classes += 1
start = x
return classesimport java.util.*;
class Solution {
public int groupStudents(int[] levels, int maxSpread) {
Arrays.sort(levels);
int classes = 1;
int start = levels[0];
for (int x : levels) {
if (x - start > maxSpread) {
classes++;
start = x;
}
}
return classes;
}
}#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int groupStudents(vector<int>& levels, int maxSpread) {
sort(levels.begin(), levels.end());
int classes = 1;
int start = levels[0];
for (int x : levels) {
if (x - start > maxSpread) {
classes++;
start = x;
}
}
return classes;
}
};Software developers at Amazon are developing a new library for natural language processing. In one of its modules, every string needs to be preprocessed in a particular manner to find the length of its longest self-sufficient proper substring. A substring is self-sufficient if every character appearing in it appears the same total number of times in the original string. A proper substring is a substring that is not equal to the whole string. Find the length of the longest self-sufficient proper substring of fullString. If no such substring exists, return 0.
Constraints
1 ≤ |fullString| ≤ 10⁵fullStringconsists of lowercase English letters
Example
fullString = "abadgdg"
answer = 4fullString = "aaaaaaa"
answer = 0解法
贪心划分：自足块是包含其内每个字符所有出现的最小连续区间。求出所有此类块；若 ≥ 2 个，答案为 max(最大块, 总长 - 最小块)。复杂度 O(n)。
def findLongestLength(fullString):
n = len(fullString)
last = {c: i for i, c in enumerate(fullString)}
blocks = []
l = 0
r = last[fullString[0]]
for i in range(n):
r = max(r, last[fullString[i]])
if i == r:
blocks.append(r - l + 1)
l = r + 1
if l < n:
r = last[fullString[l]]
if len(blocks) < 2:
return 0
total = sum(blocks)
return max(max(blocks), total - min(blocks))import java.util.*;
class Solution {
public int findLongestLength(String fullString) {
int n = fullString.length();
int[] last = new int[26];
for (int i = 0; i < n; i++) last[fullString.charAt(i) - 'a'] = i;
List<Integer> blocks = new ArrayList<>();
int l = 0, r = last[fullString.charAt(0) - 'a'];
for (int i = 0; i < n; i++) {
r = Math.max(r, last[fullString.charAt(i) - 'a']);
if (i == r) {
blocks.add(r - l + 1);
l = r + 1;
if (l < n) r = last[fullString.charAt(l) - 'a'];
}
}
if (blocks.size() < 2) return 0;
int total = 0, maxLen = 0, minLen = Integer.MAX_VALUE;
for (int b : blocks) {
total += b;
maxLen = Math.max(maxLen, b);
minLen = Math.min(minLen, b);
}
return Math.max(maxLen, total - minLen);
}
}#include <string>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
int findLongestLength(string fullString) {
int n = fullString.size();
int last[26] = {0};
for (int i = 0; i < n; i++) last[fullString[i] - 'a'] = i;
vector<int> blocks;
int l = 0, r = last[fullString[0] - 'a'];
for (int i = 0; i < n; i++) {
r = max(r, last[fullString[i] - 'a']);
if (i == r) {
blocks.push_back(r - l + 1);
l = r + 1;
if (l < n) r = last[fullString[l] - 'a'];
}
}
if ((int) blocks.size() < 2) return 0;
int total = 0, maxLen = 0, minLen = INT_MAX;
for (int b : blocks) {
total += b;
maxLen = max(maxLen, b);
minLen = min(minLen, b);
}
return max(maxLen, total - minLen);
}
};