目录
题目要求
思路：贪心
- 每次都用当前区间内的边界构造，即看到I，就放当前可用的最小值；看到D，就放当前可用的最大值。
- 证明：
- 起始区间为
[
0
,
n
]
[0,n]
[0,n]，
n
n
n为所给string大小；
- 当
s
[
0
]
=
I
s[0]=I
s[0]=I时，填入左边界
0
0
0（最小值），区间变为
[
1
,
n
]
[1,n]
[1,n]，即后续所有数都将比当前大，符合题意；
- 当
s
[
1
]
=
D
s[1]=D
s[1]=D时，填入右边界
n
n
n（最大值），区间变为
[
1
,
n
−
1
]
[1,n-1]
[1,n−1]，即后续所有数都将比当前小，符合题意。
Java
class Solution {
public int[] diStringMatch(String s) {
int n = s.length(), small = 0, large = n, idx = 0;
int[] res = new int[n + 1];
for(int i = 0; i < n; i++) {
if(s.charAt(i) == 'I') // 放最小的
res[idx++] = small++;
else // 放最大的
res[idx++] = large--;
}
res[idx] = small;
return res;
}
}
- 时间复杂度：
O
(
n
)
O(n)
O(n)
- 空间复杂度：
O
(
1
)
O(1)
O(1)
C++
class Solution {
public:
vector diStringMatch(string s) {
int n = s.size(), small = 0, large = n, idx = 0;
vector res(n + 1);
for(int i = 0; i < n; i++) {
if(s[i] == 'I') // 放最小的
res[idx++] = small++;
else // 放最大的
res[idx++] = large--;
}
res[idx] = small;
return res;
}
};
- 时间复杂度：
O
(
n
)
O(n)
O(n)
- 空间复杂度：
O
(
1
)
O(1)
O(1)
Rust
impl Solution {
pub fn di_string_match(s: String) -> Vec {
let mut res = vec![0; s.len() + 1];
let (mut small, mut large) = (0, s.len() as i32);
s.chars().enumerate().for_each(|(i, b)| if b == 'I' { // 放最小的
res[i] = small;
small += 1
} else { // 放最大的
res[i] = large;
large -= 1
});
res[s.len()] = small;
res
}
}
总结
快乐开贪，光速完成~
