You are building a simplified Tetris engine for a grid that is 10 columns wide. Pieces enter from the top, fall straight down, and come to rest as soon as any part of the piece touches the bottom of the grid or an already-settled block.
Each piece is rigid, consists of four unit squares, and never rotates. The possible piece types are Q, Z, S, T, I, L, and J. A game state starts with an empty grid.
The input to your function is a comma-separated sequence of piece placements. Each placement is encoded as a piece letter followed by a single-digit integer. The integer is the leftmost column occupied by the piece, using zero-based indexing. After each piece settles, if any row becomes completely full, that row is cleared and every row above it drops down together without changing the internal block pattern within each row.
Return the final height of the remaining settled blocks after all placements in the sequence have been processed.
Function Description
Complete the function getFinalHeight in the editor below.
getFinalHeight has the following parameter:
String sequence: a comma-separated sequence of piece placements such as"I0,I4,Q8"Returnsint: the final stack height after processing all placements and clearing all complete rows
Constraints
- The grid width is always
10. - Each placement is one of
Q,Z,S,T,I,L, orJ, followed by a single-digit zero-based column index. - Pieces never rotate and always use the fixed orientations shown in the source prompt.
- The input sequence is valid, and every placement fits within the board.
- You may assume no test case produces a final height greater than
100.
Example 1
Input:
sequence = "I0,I4,Q8"Output:
1Explanation:
The three pieces fill the entire bottom row, so that row is cleared. The remaining settled blocks have height 1.
Example 2
Input:
sequence = "T1,Z3,I4"Output:
4Explanation:
No row becomes completely full, so nothing is cleared. The final settled structure has height 4.
Example 3
Input:
sequence = "Q0,I2,I6,I0,I6,I6,Q2,Q4"Output:
3Explanation:
The first row clears after the early placements, and a later row clears again after additional pieces settle. The final remaining structure has height 3.
解法
维护每列当前高度。对每个落子枚举它占用的格子(用形状偏移表)，下落高度 = max(各占用列底部 - 形状底部偏移)；放置后，更新每列高度，检查可能完整的行并消除(被消行以上的所有方格整体下降一格)。最终答案是各列高度最大值。时间复杂度 O(K·W·H)，K 为落子数，W=10，H≤100。
def getFinalHeight(sequence: str) -> int:
SHAPES = {
'Q': [(0, 0), (0, 1), (1, 0), (1, 1)],
'Z': [(0, 0), (0, 1), (1, 1), (1, 2)],
'S': [(0, 1), (0, 2), (1, 0), (1, 1)],
'T': [(0, 0), (0, 1), (0, 2), (1, 1)],
'I': [(0, 0), (0, 1), (0, 2), (0, 3)],
'L': [(0, 0), (1, 0), (2, 0), (2, 1)],
'J': [(0, 1), (1, 1), (2, 0), (2, 1)],
}
W = 10
grid = [[False] * W for _ in range(200)]
heights = [0] * W
for token in sequence.split(','):
if not token:
continue
piece, col = token[0], int(token[1])
cells = SHAPES[piece]
bottom = {}
for dr, dc in cells:
bottom[dc] = max(bottom.get(dc, -1), dr)
base = 0
for dc, br in bottom.items():
base = max(base, heights[col + dc] - br)
for dr, dc in cells:
grid[base + dr][col + dc] = True
top = base + max(dr for dr, _ in cells)
for dr, dc in cells:
heights[col + dc] = max(heights[col + dc], base + dr + 1)
r = base
while r <= top:
if all(grid[r]):
del grid[r]
grid.append([False] * W)
top -= 1
for c in range(W):
if heights[c] > r:
heights[c] -= 1
for c in range(W):
h = 0
for rr in range(heights[c] + 1):
if rr < len(grid) and grid[rr][c]:
h = rr + 1
heights[c] = h
else:
r += 1
return max(heights)class Solution {
int getFinalHeight(String sequence) {
int[][][] SHAPES = new int[128][][];
SHAPES['Q'] = new int[][]{{0,0},{0,1},{1,0},{1,1}};
SHAPES['Z'] = new int[][]{{0,0},{0,1},{1,1},{1,2}};
SHAPES['S'] = new int[][]{{0,1},{0,2},{1,0},{1,1}};
SHAPES['T'] = new int[][]{{0,0},{0,1},{0,2},{1,1}};
SHAPES['I'] = new int[][]{{0,0},{0,1},{0,2},{0,3}};
SHAPES['L'] = new int[][]{{0,0},{1,0},{2,0},{2,1}};
SHAPES['J'] = new int[][]{{0,1},{1,1},{2,0},{2,1}};
int W = 10;
boolean[][] grid = new boolean[200][W];
int[] heights = new int[W];
for (String token : sequence.split(",")) {
if (token.isEmpty()) continue;
int[][] cells = SHAPES[token.charAt(0)];
int col = token.charAt(1) - '0';
int[] bottom = new int[4]; Arrays.fill(bottom, -1);
int maxDc = 0;
for (int[] c : cells) { maxDc = Math.max(maxDc, c[1]); }
int[] bot = new int[maxDc + 1]; Arrays.fill(bot, -1);
for (int[] c : cells) bot[c[1]] = Math.max(bot[c[1]], c[0]);
int base = 0;
for (int dc = 0; dc <= maxDc; dc++) {
if (bot[dc] >= 0) base = Math.max(base, heights[col + dc] - bot[dc]);
}
for (int[] c : cells) grid[base + c[0]][col + c[1]] = true;
for (int[] c : cells) heights[col + c[1]] = Math.max(heights[col + c[1]], base + c[0] + 1);
int top = base;
for (int[] c : cells) top = Math.max(top, base + c[0]);
int r = base;
while (r <= top) {
boolean full = true;
for (int c = 0; c < W; c++) if (!grid[r][c]) { full = false; break; }
if (full) {
for (int rr = r; rr < grid.length - 1; rr++) grid[rr] = grid[rr + 1];
grid[grid.length - 1] = new boolean[W];
top--;
for (int c = 0; c < W; c++) {
int h = 0;
for (int rr = 0; rr < grid.length; rr++) if (grid[rr][c]) h = rr + 1;
heights[c] = h;
}
} else r++;
}
}
int ans = 0;
for (int h : heights) ans = Math.max(ans, h);
return ans;
}
}class Solution {
public:
int getFinalHeight(string sequence) {
unordered_map<char, vector<pair<int,int>>> SHAPES = {
{'Q', {{0,0},{0,1},{1,0},{1,1}}},
{'Z', {{0,0},{0,1},{1,1},{1,2}}},
{'S', {{0,1},{0,2},{1,0},{1,1}}},
{'T', {{0,0},{0,1},{0,2},{1,1}}},
{'I', {{0,0},{0,1},{0,2},{0,3}}},
{'L', {{0,0},{1,0},{2,0},{2,1}}},
{'J', {{0,1},{1,1},{2,0},{2,1}}}
};
const int W = 10;
vector<vector<int>> grid(200, vector<int>(W, 0));
vector<int> heights(W, 0);
string token;
stringstream ss(sequence);
while (getline(ss, token, ',')) {
if (token.empty()) continue;
auto& cells = SHAPES[token[0]];
int col = token[1] - '0';
unordered_map<int,int> bot;
for (auto [dr, dc] : cells) bot[dc] = max(bot.count(dc) ? bot[dc] : -1, dr);
int base = 0;
for (auto [dc, br] : bot) base = max(base, heights[col + dc] - br);
for (auto [dr, dc] : cells) grid[base + dr][col + dc] = 1;
for (auto [dr, dc] : cells) heights[col + dc] = max(heights[col + dc], base + dr + 1);
int top = base;
for (auto [dr, dc] : cells) top = max(top, base + dr);
int r = base;
while (r <= top) {
bool full = true;
for (int c = 0; c < W; c++) if (!grid[r][c]) { full = false; break; }
if (full) {
grid.erase(grid.begin() + r);
grid.push_back(vector<int>(W, 0));
top--;
for (int c = 0; c < W; c++) {
int h = 0;
for (int rr = 0; rr < (int)grid.size(); rr++) if (grid[rr][c]) h = rr + 1;
heights[c] = h;
}
} else r++;
}
}
return *max_element(heights.begin(), heights.end());
}
};